1
$\begingroup$

Let $G$ be a connected planar graph with $p$ vertices, where $p \geq 3$. Let $t$ denote the number of vertices in $G$ with degree less than $6$.

Prove that if $G$ has no cycles then $t \geq \frac{4p+2}{5}$.

I tried using the inequality $p \leq 3p - 6$ with Euler's formula: $p - q + 1 = 2$ (where $p$ is the number of vertices in G, $q$ is the number of edges in G, $f$ is the number of faces in G) but couldn't figure it out. Thanks in advance!

  • 0
    What do you mean with (i) $p\le 3p-6$, (ii) "Euler's"-what and (iii) where does $q$ surprisingly come from?2012-12-11
  • 0
    Sorry - (i) is an identity for connected planar graph with p >=3 vertices and q edges. (ii) Euler's formula: Let G be a connected graph with p vertices and q edges. If G has a planar embedding with f faces, then p - q + f = 2. (f = 1 in this case with only 1 outer face for a tree).2012-12-11
  • 0
    (i) is not an identity, it's an inequality, and $q$ does not appear in it the way you have written it.2012-12-11

1 Answers 1

1

If $G$ is connected and has no cycles then (as you know) $p=q+1$. Also, the sum of the degrees of the vertices is $2q$. Break that sum into two parts, one involving the vertices of degree less than $6$, the other, the vertices of degree at least $6$, and make estimates of both parts of the sum. Come back (showing your progress) if that doesn't get you there.

  • 1
    Ah, I got it! $t + 6(p-t) \le 2q$ Thank you!2012-12-12