3
$\begingroup$

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:

$V-E+F=2$

$E\leq 3V-6$

$3F\leq 2E$

2 Answers 2

4

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.

  • 0
    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.2012-12-09
3

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.