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