The question is: "Prove that if G is a connected planar simple graph, then G has a vertex of degree at most five."

It baffles me because a connected planar simple graph CAN have a vertex of degree more than five.

Am I misunderstanding the wording?

I mean what if I just draw a hexagon with 6 vertices and connect them all to a 7th vertex in the centre?

  • 1
    $\begingroup$ Note that the question asks for "a vertex" to have degree less than six, rather that for every vertex to have small degree. $\endgroup$ Dec 1, 2017 at 7:38
  • $\begingroup$ In your example, the first six vertices each have degree 3. There need only be one vertex with degree less than 6. $\endgroup$
    – JOF14
    Dec 1, 2017 at 7:39


Browse other questions tagged .