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.

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.$

share|improve this question
add comment

1 Answer 1

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.)

share|improve this answer
    
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
add comment

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.