§ Euler tours
§ Tucker's proof: undirected graph with all even degree has an euler tour
I find this proof much more intuitive because it's extremely clear where
the even condition is used.
It's super clear why we need all vertices to be even degree; You can't pair
up vertices otherwise!
- For each vertex , arbitrarily pair edges incident at to get chains
u --- v --- w.
- Connect chains to get cycles.
- Find a spanning tree of cycles to get an euler tour, where we have an edge between two cycles if they share a common vertex.