This is one example of a problem where a "greedy" algorithm works. At 07:48 PM 2/3/2005, Steve Gray wrote:
Very nice. You might have mentioned the situation where the path you just created did not visit some vertices at all, but that does not invalidate the argument.
Steve Gray
----- Original Message ----- From: "Michael Kleber" <michael.kleber@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Cc: <thane@best.com> Sent: Thursday, February 03, 2005 7:20 PM Subject: Re: [math-fun] Question about graphs
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.