[Math] Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite

Question

Let $G$ be a simple connected plane graph where $v>2$, and $G^*$ is its dual graph.
Prove that if $G$ is isomorphic to $G^*$, then $G$ is not bipartite.

I know that $G$'s number of faces is equal to its number of vertices, but is this fact any use for this question? Would I also have to use the Euler's formula, $v-e+f=2$?

Thanks in advance.

Answer 1

In this problem, I shall assume that $G$ is a simple graph. There are counterexamples if $G$ is not simple. Indeed, there is a counterexample for any given number of vertices $v\geq 2$ (consider any star graph and replace every edge by a pair of parallel edges).

Hints:

• If $G \cong G^*$, how many edges does $G$ have as a function of the number of faces?
• What is the sum of the degrees of all faces?
• There is a face of degree exactly $3$.

Solution:

Suppose that $G\cong G^*$. If we can show that there is a face of $G$ of degree $3$, then this face is bounded by three edges forming a $3$-cycle of $G$. Since a bipartite graph cannot have an odd cycle, $G$ is not bipartite.

Now, to show that $G$ has a face of degree $3$, we recall the Euler characteristic $v-e+f=2$, where $v$ is the number of vertices of $G$, $e$ the number of edges, and $f$ the number of faces. Since $G$ is a simple graph, a face of $G$ must have degree at least $3$ (otherwise $G$ has a loop or parallel edges). Since $G\cong G^*$, $v=f$. That is, $e=2f-2$. Now the sum of the degrees of $f$ is $2e=4f-4$. Hence, there exists a face of degree at most $\frac{4f-4}{f}=4-\frac{4}{f}<4$. That is, $G$ has a face of degree at most $3$. This face must then have degree $3$.

For every $v\geq 4$, there is a simple planar graph $G$ on $v$ vertices such that $G$ is self-dual. The wheel graphs are such examples.