Proving Graph Theory Question

Since G is not bipartite, G contains an odd cycle C. Let $F_{1},F_{2},......,F_{k}$ be the faces inside C in the planar embedding. Consider the sum of the degrees of these face.

• Each edge in C is being counted once.
• Let D be the set of edges on any boundary of any $F_{i}$, but not on C.

Each edge in D is counted twice.

So $sum_{i}$ $deg(F_{i})$ = $|E(C)| + 2|D|$

Since $|E(C)|$ is odd and $2|D|$ is even,

$sum_{i}$ $deg(F_{i})$ is odd, so $deg(F_{i})$ must be odd for some $i$

So at least one face inside C has odd degree.

The same argument can be used to show that at least once face outside C has odd degree.