Thanks, Chris. The graphs I'm interested in are finite and connected, and I want to travel each edge once. Sometimes I forget to mention the "secondary" attributes of a situation I'm working on (not that anything in math is really secondary). The path I want is called an Eulerian Cycle according to the CRC encyclopedia, but it doesn't quite state the theorem or give a reference. Steve ----- Original Message ----- From: "Chris Landauer" <cal@rush.aero.org> To: <math-fun@mailman.xmission.com> Cc: <cal@rush.aero.org> Sent: Thursday, February 03, 2005 5:26 PM Subject: [math-fun] graph question
hihi. all -
let's start by stating the problem in a way that can be solved
the graph certainly needs to be finite and connected
in addition, you also have to limit the number of times each edge can be retraced, or else it is trivial to draw any connected finite graph with a continuous path, whether or not there are odd order vertices (pick any one vertex - connected means there is a path, so just draw all the paths from
that
vertex to the others and back)
the usual restriction is to limit each edge to exactly one traversal (so the order of a vertex is the total number of arrivals and departures it encounters in the continuous path), which is called an eulerian path (the seven bridges of koenigsburg apparently brought the problem to his attention)
there are no finite graphs with exactly one odd order vertex
it is clear that any eulerian path in a graph with two odd order vertices will necessarily start at one of them and end at the other
also, it is clear that any eulerian path for a graph with no odd order vertices must end at the same vertex at which it starts
i expect there is a reasonably straightforward induction proof - it is certainly an old theorem
more later, cal
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun