Jtdylktuy

How would I go about doing this proof I am not very knowledgeable about graph theory I know the definitions of planar and bipartite and dual but how do you make these connection

So $G$ is planar and eulerian. We must prove $G'$ is bipartite. Asume $G'$ is not bipartite. Now I want you to forget about the fact that $G'$ is the dual of $G$. Just think of $G'$ as a normal graph in which the vertices of $G'$ are drawn as vertices and not as the faces of $G$.

Since $G'$ is not bipartite it has an odd cycle, one of the faces inside that odd cycle must therefore have an odd number of edges. That face is a vertex of odd degree in $G''$,so $G''$ is not eulerian. Now,$Gcong G''$ so $G$ is not eulerian, a contradiction. The contradiction comes from assuming $G'$ is not bipartite.

A key step is the fact $Gcong G''$.

Let $G$ be a planar Eulerian graph, and consider a particular planar diagram of $G$. There is an Eulerian circuit that does not pass "through" vertices, but instead always takes a hard left or right turn.

While there is probably some argument involving depth-first traversals, one can also construct such an Eulerian circuit by starting with any Eulerian circuit then performing the following kind of local modification to the circuit whenever the circuit crosses over itself (which happens exactly when the circuit fails to make a hard turn).

If we think of the circuit as being a curve in the plane, we can push it slightly away from the vertices to get an embedded closed curve. By the Jordan Curve Theorem, this curve separates the plane into two components. The dual graph's vertices are partitioned into two sets depending on which side of the circuit the vertex lies on, and each edge of the dual graph crosses the circuit transversely in one point. Hence, the dual graph is a planar bipartite graph.

Here is a worked example of the dual of on octahedral graph, with the blue curve being the pushed-off embedded Eulerian circuit, and with the cyan and green vertices representing the two partitions of the bipartite graph:

For the converse, you can take small blue circles around each green vertex to get a multicurve. Then around each vertex in the dual graph you can join them in such a way to get an Eulerian circuit of the dual. Or just note that each face in a planar bipartite graph has an even number of sides.

(It seems there should be a way to think about all of this in terms of (co)homology with $mathbb{Z}/2mathbb{Z}$ coefficients and Poincaré duality.)

A possible simplification to the above argument could be that Eulerian implies each vertex has even degree. Then, one can replace each vertex of degree $2n$ with $n$ vertices of degree $2$ in a "starburst" pattern. This is a planar graph composed entirely of circles. By the Jordan curve theorem you can $2$-color the regions between the circles, meaning the regions on either side of a circle have opposite colors. The coloring partitions the vertices of the dual graph into two parts, and again edges cross the circles, so the dual is bipartite.

This is rehashing a proof that the dual of a planar graph with vertices of only even degree can be $2$-colored. For example the shadow of a knot diagram.