2

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.

Community
  • 1
Aurasphere
  • 131
  • 3
    Look at the 9-star graph. You are right that the MAXIMUM degree will be 9 > 6, but the MINIMUM degree is found at the other end of the edges and equals 1. The claim is not that EVERY degree < 6, just that there is always one. – Vincent Jul 15 '16 at 08:06
  • The proof you quote misses at least one '='-sign and perhaps some other symbols which I can not reverse engeneer. Can you go back to the original source and edit it? – Vincent Jul 15 '16 at 08:06
  • BTW don't feel stupid for not immediately 'seeing' that this is true - it is really a somewhat surprising fact that really needs a proof. The proof (which can be found in some of the 'Related' questions in the sidebar) relies on Euler's formula v - e + f = 2 which in itself is not at all obvious at first sight. – Vincent Jul 15 '16 at 08:09
  • Thank you, now I understand... If you feel like posting an actual answer I will accept it. – Aurasphere Jul 15 '16 at 08:14

1 Answers1

6

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.

Vincent
  • 10,614