Thane, We met, or at least we heard each other's pitch, at the Experimental Math workshop in Oakland about a year ago. Everyone: Thanks for answering. I will quote from Frank Harary's 1969 book "Graph Theory." He gives a one-page proof which I omit. (It's a good thing math proofs don't become wrong with time.) "As we have seen in Chapter 1, Euler's negative solution of the Koenigsberg Bridge problem constituted the first publicized discovery of graph theory. The perambulatory problem of crossing bridges can be abstracted to a graphical one: Given a graph G, is it possible to find a walk that traverses each line exactly once, goes through all points, and ends at the starting point? A graph for which this is possible is called eulerian. Thus, an eulerian graph has an eulerian trail, a closed trail containing all points and lines. Clearly, an eulerian graph must be connected. Theorem 7.1 (page 64): The following statements are equivalent for a connected graph G: 1. G is eulerian; 2. Every point of G has even degree; 3. The set of lines of G can be partitioned into cycles." (end of quote) This is a positive answer to the question I posed (but from which I left out several crucial elements). Steve Gray ----- Original Message ----- From: "Thane Plambeck" <thane@best.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, February 03, 2005 4:45 PM Subject: Re: [math-fun] Question about graphs
A connected graph has an Euler trail if and only if it has at most two vertices of odd degree.
See for example, JA Bondy & USR Murty, Graph Theory with Applications, pg 52.
If there's no online proof (it's not hard to prove) write one and put it on a web site!
Steve Gray wrote:
Marc, Thanks for answering. The graphs I am concerned with are all connected. The path I want is called an Eulerian Cycle, according to Eric's Encyclopedia, which does not quite answer my question. Now if I can find my copy of Harary, the answer might be there.
----- Original Message ----- From: "Marc LeBrun" <mlb@fxpt.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, February 03, 2005 3:21 PM Subject: Re: [math-fun] Question about graphs
Neat question!
=Steve Gray An obvious threorem in simple graph theory says that no graph with
(no)
An extra negation may have slipped in here: (YOU'RE CORRECT) ^^
more than two nodes of odd order can be drawn in one continuous path. Is there a theorem saying that any graph with two, one, or zero nodes
of odd
order can always be drawn in one continuous path? A yes/no answer would be nice,
No, not without also requiring the graph to be connected.
and a reference would be even nicer.
I'll have to leave that to the professionals.
Thanks for any info.
"Enjoy"!
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck http://www.plambeck.org/ehome.htm
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun