# Connected planar graph with girth $\leq$ 6 $\rightarrow$ exists at least one vertex degree $\leq 2$

Having trouble with how to approach this question:

Suppose $G$ is a connected planar graph having girth at least $6.$ Prove that $G$ has at least one vertex with degree at most $2.$

-

As you initially asked for how to approach this proof:

$(1)$ You can start by assuming $G$ is a connected planar graph having girth at least $6$. Given such a $G$, then, you need to prove $G$ has at least one vertex with degree at most $2$.

$(2)$ You can also prove the statement in its equivalent contrapositive form:
Assume $G$ does not have a vertex with degree at most 2, and prove that then $G$ cannot be a connected planar graph having girth at least $6$. Proving this is equivalent to proving $(1)$.
(That is, you can prove any statement $p \rightarrow q$ by proving the contrapositive: $\lnot q \rightarrow \lnot p$, as these expressions are logically equivalent.)

$(3)$ Finally, you can use an indirect proof:
Assume that $G$ is a connected planar graph having girth at least $6$, AND assume, for the sake of contradiction, that $G$ does not have any vertex with degree at most $2$ (in other words, that for every vertex $v$ in $G$, the degree of $v\geq 3$).
With this approach, the task would then be to derive a contradiction. Upon reaching a contradiction, you can then conclude that if $G$ is a connected planar graph with girth at least $6$, then it cannot be the case that $G$ has no vertex of degree at most $2$. In short, it then follows that $G$ must have at least one vertex of degree at most $2$.

Whatever approach you use in your proof, you'll need to use the definition of a connected planar graph, and one that has girth at least $6$ (where the girth of a graph is the length of its shortest cycle).

You may also need to use Euler's formula as it relates to planar graphs: $$v-e + f = 2,$$ where $v$ is the number of vertices of $G$, $e$ the number of edges of $G$, and $f$ the number of faces. (In planar graphs, the "faces" are the number of regions bounded by edges, including the outer, infinitely large region.)

-
With no hypotheses about the number of faces, I don't see how Euler's formula will help. (Granted, I haven't thought very long about the problem.) – Austin Mohr Nov 22 '12 at 3:29
Here's an additional hint. Since the girth is at least six, that means $\deg f \ge 6$ for each face $f$. Additionally, if you assume that $\deg v \ge 3$ for each vertex $v$, you can use the Euler's formula to push for a contradiction. – EuYu Nov 22 '12 at 14:53
How would to relate Euler's formula to girth? – Help Nov 22 '12 at 22:39