I'm trying to study for my combinatorics exam and this was a suggested problem.

Let $G$ be a planar graph on $V\geq 2$ vertices. How can we prove that $G$ has at least $2$ vertices whose degrees are at most $5$?

Here are some things about planar graphs that I do know:


$E\leq 3V-6$

$3F\leq 2E$


Suppose every vertex, with at most one exception, has degree at least $6$. Do you know a relation between the degrees of the vertices of a graph and the number of edges? That, together with one of the relations you have written, should do it.

  • $\begingroup$ So would the at most one exception be less than 6? $\endgroup$ – Wooooop Dec 8 '12 at 22:38
  • $\begingroup$ Suppose every vertex, with at most one exception, has degree at least 6. Then, 2E =< 2(3V-6) = 6V-12; Sum (deg V) >= 6(V-1) = 6V-6; We see that 6V-12 > 6V-6, thus there are at lease two vertices whose degrees are at most 5. Is this the solution? I still can't see how we have two vertices that are at most 5. $\endgroup$ – Wooooop Dec 8 '12 at 22:43
  • $\begingroup$ On the hypothesis, the sum of the degrees is at least $6V-6$, so $E\ge3V-3$, contradicting $E\le3V-6$. Thus, the hypothesis fails; there must be more than one exceptional vertex. $\endgroup$ – Gerry Myerson Dec 9 '12 at 6:30

Hint: Have you tried proving this by induction on $V$?

The objective is to prove $P(n) = $ "Any planar graph $G$ with $V \geq 2$ vertices, there exist two vertices of degree $\leq 5$." (You need to show that two distinct such vertices exist, and that will suffice.)

  • $(1)$ Start with base-case: Show that for $G$ with $V = 2$ vertices, each vertex has degree 2. (That is, $P(2)$ is trivially true).

  • $(2)$ Assume $P(k)$ is true when $V = k$.

  • $(3)$ Then, show that if one more vertex is added to $G$, so $G$ has $V = k + 1$ vertices, it follows from $P(k)$ that $P(k+1)$ is also true.

Then you will have shown that $P(n)$ is true.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.