# Prove planar embedding has a vertex of degree at most 3 or a face of degree 3

Prove that every planar embedding has either a vertex of degree at most 3 or a face of degree 3.

This is a problem in my course notes without a solution. I tried this problem but could not narrow down an invariant that covers all cases. Could someone provide a sketch of a proof? Or give a hint of a useful invariant?

-
By a face of degree 3 do you mean one with exactly three sides? There exist plane graphs of arbitrarily high degree (lots of loops) whose only faces have sides of length 1 or 2. There are also plane graphs with exactly 2 vertices with arbitrarily high degree whose faces all have two sides. – Joseph Malkevitch Jul 28 '11 at 15:20

I find it a little easier to deal with embeddings in the sphere.

Step one: by imagining a pebble on each side of each edge, and counting pebbles two different ways, prove that if every face has degree at least 4, then $2E\ge4F$ (where $E$ is the number of edges and $F$ is the number of faces).

Step two: by imagining a pebble at each end of each edge, and counting pebbles two different ways, prove that if each vertex has degree at least 4, then $2E\ge4V$ (where $V$ is the number of vertices).

Step three: combine these to get $4E\ge4(F+V)$ and use what you know about $F+V$ to get a contradiction.

-
Why not just use $\sum degree(f)$ = $2E$ therefore $2E \geq 4F$? The same applies for vertex degree as well. – Mark Jul 28 '11 at 19:59
@Mark, if you already know the degrees add up to $2E$, fine, use it. The pebbles are one way to prove the degrees add up to $2E$, in case you didn't know or weren't allowed to use that fact. – Gerry Myerson Jul 29 '11 at 0:08
Most difficult part of this proof is finding all the tools such as searching up the necessary theorems. – A_for_ Abacus Jul 18 '14 at 3:48

A hint: If your graph has a vertex of degree $\leq3$ you are done. If not, the embedding describes a "polyhedron" all whose vertices have a degree $\geq4$. There is a famous theorem about the combinatorial structure of polyhedra; maybe it helps.

-
I assume the theorem you are talking about which deals with polyhedra is Steinitz's Theorem, which requires that the plane graph be 3-connected, and it deals with convex polyhedra. With suitable assumptions results of this type can be derived from Euler's formula: For a connected plane graph, V + F - E = 2. – Joseph Malkevitch Jul 28 '11 at 15:33