1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – efxgamer Mar 2 '17 at 2:40
  • 1
    $\begingroup$ 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. $\endgroup$ – Joffan Mar 2 '17 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.