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
    (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