Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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