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, prove 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 \Leftarrow 3p-6$, $2p \Leftarrow 3p-6$?
But after this I'm kind of stuck on where to proceed. Help would be appreciated.
Best Answer
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$.