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.$
[Math] Connected planar graph with girth $\leq$ 6 $\rightarrow$ exists at least one vertex degree $\leq 2$
graph theoryproof-writing
Best Answer
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.)