1
$\begingroup$

let $G$ be a planar graph

Prove that in any planar embedding of $G$, number of faces with odd degree is even. Also, prove that if G is not bipartite, then there are at least 2 faces with odd degree.

So I'm feeling really lost here. I feel like the first part should have to do with the fact that the number of vertices with odd degree is even? not really sure where to go from there. Since second part extends from first part, understanding the first part would help me out a lot.

$\endgroup$
  • 1
    $\begingroup$ Put a pebble on each side of each edge, and count the total number of pebbles two different ways. $\endgroup$ – Gerry Myerson Mar 27 '15 at 11:56
  • $\begingroup$ What's the degree of a face? $\endgroup$ – Zilin J. Mar 27 '15 at 12:44
  • $\begingroup$ @roy, presumably the number of edges bounding the face. $\endgroup$ – Gerry Myerson Mar 28 '15 at 6:28
3
$\begingroup$

This is an expansion on what Gerry Myerson wrote, but the sum of the degrees of all faces is twice the number of edges. Thus this sum must be even.

Then, if a graph is not bipartite, it is not 2-colorable and thus has a cycle of odd degree. Because of the point above, it must have two such cycles.

$\endgroup$

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.