§ 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.
- For each vertex v, arbitrarily pair edges incident at v 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.
It's super clear why we need all vertices to be even degree; You can't pair
up vertices otherwise!
§ References