I'm trying to study (by myself) planar graphs. On the book I'm reading, I came across this sentence about the 5-coloring problem that I really don't understand:
Lemma 5.8.15. Every planar graph has a vertex of degree at most five.
Proof. By contradiction. If every vertex had degree at least 6, then the sum of the vertex degrees is at least 6v, but since the sum of the vertex degrees equals 2e, by the Handshake Lemma (Lemma 5.2.1), we have e 3v contradicting the fact that e 3v <= 6 < 3v by Theorem 5.8.6.
I don't get why a planar graph has a vertex of degree at most five. If I take the 9-star graph there will be a node with degree 9 and the graph will still be planar so the maximum degree is greater than 6.
Can anyone explain this to me?
Thank you.
No the claim is not that the maximum degree is 5 (that would be wrong by exactly your reasoning) but that the minimum degree is 5 or less. Some planar graphs have minimum degree 1, some minimum degree 2, etc but no planar graph has minimum degree 6. This is not obvious, hence we need a proof.
Minimum degree 6 means 'every vertex has degree at least six', that is why the book starts its proof by looking at a hypothetical graph where every vertex has degree at least six and proceeds to show that no such graph can exist.