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.
Best Answer
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.