Thread: Graph Theory Probe

Could someone please assist with the following question:


Show that every nontrivial connected graph has a closed spanning walk that contains
every edge exactly twice.

Induct on the number of verticies.
It's true for a (the) connected graph with 2 vertices. You can check the same for 3 verticies.
Suppose it's true for all simple connected graphs of N or fewer verticies, N>=3.
Let G be any connected graph with N+1 verticies.
Pick a vertex v in G.
Suppose G - v breaks into connected graphs G1, G2, G3, .. Gm.
If can show how to do it with those graphs individually, so that you start and end at v in <Gi Union {v}>, then you can do it for all of them, and hence for G.
That's because you'd start at v, go through G1 returning to v, then go through G2 returning to v, etc..

How how do you do it for one?
Suppose {x1, x2, ... xn} are v's neighbors in G1.
First note that v has has at least one neighbor in G1 (the original G wouldn't be connected otherwise).
If v has more than one neighbor in G1, then begin the walk with the walk (v, x1, v, x2, v, x3, ...., v, x(n-1), v}.
That covers all those edges exactly twice, and so just one neighbor of v in G1, xn, remains.
Walk v to xn, but then do a cover-each-edge-exactly-twice spanning walk though G1 starting and ending at xn (induction!)
When that walk returns to xn, then return to v.
That covers the edge (v,xn) exactly twice, and all the edges in G1 exactly twice.
Thus have done it for <G1 Union {v}>.
Now, as above, repeat that process, doing v with G2, then v with G3, ... and v with Gn.
Then have done it for all of G: a spanning walk of G, starting and ending at v, with every edge crossed exactly twice.
That completes the induction and so proves the claim.