Proving a graph is not bipartite Let $G$ be a simple planar graph with at least $2$ vertices, and let $G^*$ be the dual of a planar embedding of $G$. Prove that if $G$ is isomorphic to $G^*$ , then $G$ is not bipartite.
I have absolutely no idea how to start this, can someone give me some nice hints? TY.
 A: If it is bipartite you can color its vertices (alternating) black and white. Since it is isomorphic to its dual then you can also color alternating red and green the faces (in a planar embedding). This means that no vertex has degree greater than three. So the graph must be a disjoint union of a bunch of cycles together with chains. If a cycle has more than two edges then the dual and therefore the graph has vertices with more than two edges. So, only cycles of two vertices. There cannot be chains because then the dual has loops and a bipartite can't have them. There cannot be many disjoint cycles because we get in the dual and then in the graph vertices with more than two edges. So it is only one cycle with two edges. But this works, isn't it? 
I guess the problem should say "more than $2$ vertices".
Oh! It says, simple graph. This is not a simple graph. So, ok. Then it is fine. The cycle with two edges doesn't work either. QED the graph cannot be bipartite.
A: Let $n$ be the number of vertices of $G$. Then $G^*$ also has $n$ vertices which means $G$ has $n$ faces. Using $V-E+F=2$, we get
$$E=2n-2 \,.$$
If $n=2$ then $V=E=2$ which is not possible. 
Otherwise, the graph is planar and bipartite*, we have $E\leq 2V-4$, and hence
$$2n-2 \leq 2n-4$$
contradiction.
*We actually only used that $G$ doesn't have any $3$-cycle. 
