# Proving that $G$ has a vertex of degree at most $3$ for planar graph.

Edit: Not homework/assignment, review for an exam. Let $$G$$ be a connected planar graph with a planar embedding that has $$n$$ vertices, $$m$$ edges, and $$n$$ faces.

Knowing that $$m = 2n - 2$$, I proved it earlier,

Prove $$G$$ has a vertex of degree at most $$3$$.

My proof was as follows:

Proof by contradiction, assume every vertex in $$G$$ has at least $$4$$. Then by the handshake lemma, we know that $$2p = q$$ where $$p$$ are vertices and $$q$$ are edges.

Since every planar graph must satisfy $$q \le 3p-6$$, $$2p \le 3p-6$$?

But after this I'm kind of stuck on where to proceed. Help would be appreciated.

If you know that the edges $m=2n-2$, then the sum of the vertex degrees is $2m = 4n-4$.

Then by the pigeonhole principle there must be some vertex with degree less than $4$, since all vertices having degree $4$ would lead to a sum of $4n>4n{-}4$.

• thanks for your answer, following up with my question, is there any way to relate faces to cycle length in planar graphs? Example, if there are 2 faces, then G has a cycle of length 3, what could I use to relate this. Mar 2, 2017 at 2:40
• It's reasonably obvious that the edges of a face contain a cycle, but not all cycles are the edges of a face, and you can also have edges that delimit a face but are not on a cycle. So you 'd probably need a specific question to get a useful answer here. Mar 2, 2017 at 2:45