Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
So would the at most one exception be less than 6? –  Wooooop Dec 8 '12 at 22:38
    
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. –  Wooooop Dec 8 '12 at 22:43
    
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. –  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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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