3
$\begingroup$

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?

  • 0
    By $a$ fa$c$e of degree 3 do you me$a$n one with exactly three sides? There exist plane graphs of ar$b$itrarily 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 ar$b$itrarily high degree whose fa$c$es $a$ll have two sides.2011-07-28

2 Answers 2

2

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.

  • 0
    Most difficult part of this proof is finding all the tools such as searching up the necessary theorems.2014-07-18
0

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.

  • 0
    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.2011-07-28