## § 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.