1. 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.

2. Re: Graph Theory Probe

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!)