§ Dual of Planar Euler graph is bipartite

§ Proof by contradiction

• Euler graph is a graph with an euleian circuit, so we pass through every edge exactly once and return to the node we started from.
• Alternatively, every node has even degree. Consider the cycle as starting at some vertex v. To pass through all edges adjacent to v must mean that every time we leave v on a previously unused v->_ we must return back to v via a unique edge _->v. This allows us to pair edges together uniquely, giving us an even number of edges at v.
• This argument works at any generic v, since we can think of a cycle as starting from any vertex.
• Thus, every vertex of G has even degree.
• Consider the dual graph H := G*.
• Suppose H is not bipartite, so H has an odd length cycle O.
• Let K := H* be the dual of H. Consider the face of H that is bounded by the odd length cycle O, call it F(O). This face F(O)has an odd number of neighbours, one for each edge of O. So an number of edges in K connect F(O) to its neighbours. Thus, K has a vertex with an odd number of edges indicent on it.
• However, K = H* = G** = G. This implies that G has a vertex with an odd number of neighbours, contradicting its eulerian nature.

§ Constructive proof

• Consider a graph embedding. Since the graph is eulerian, we get a path/closed curve p: S^1 -> R^2 that traverses the graph along its euler tour.
• If the closed curve p has self-intersections, remove them by gently "spreading" p.
• This gives us two regions on the sphere, one inside the curve and one outside the curve (by jordan curve theorem).

• Key takeaway: Euler graphs are graphs you can draw with a pen.

§ How this is different from hamiltonian circuit

Consider:

a----------b
|          |
f----------c
|          |
e----------d

• The cycle a->b->c->d->e->f->a is hamiltonian.
• There is no eulerian cycle since f has odd degree. So if we start from f, it is impossible to return to f.
• So hamiltonian circuits do not correspond (at least in this way) to geometry.