This is easy enough to prove that this thread should include a proof itself, not just a reference to one. If the graph has zero odd-degree vertices, put your pencil down anywhere and just start drawing, always picking any unused edge. Each time you pass through a vertex, you use up two of its edges, so the number of edges available everywhere always remains even, and you will only "get stuck" upon returning to your starting vertex, where you used up one edge in your initial departure. At this point you might be done, but if not, the path you just created must visit some vertex where not all the edges were used up. (That's what "connected" means.) In this case, enlarge your cycle by "splicing in" another cycle, constructed the same way: start at a vertex on your path with an unused edge, and travel any way you want along unused edges; parity shows that you can only get stuck when you return to the vertex where your splice began. Keep splicing until all the edges are used up. If your graph has two odd-degree vertices, start at one of them and do the same; you're guaranteed to eventually "get stuck" at the other one. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.