2
$\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, 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.

$\endgroup$

1 Answer 1

2
$\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$
2
  • $\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, 2017 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, 2017 at 2:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .