Simple graph theory answer needed.

[Steve Gray]

An obvious threorem in simple graph theory says that no graph with no 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, and a reference would be even nicer. Thanks for any info.

Steve Gray

[Stephen Montgomery-Smith]

For graphs with one node of odd order, the answer is yes and no.

Stephen

[Ken Pledger]

In article <aia501d3n3ml9gfqm...@4ax.com>,
Steve Gray <ste...@adelphia.net> wrote:

Well, if you can exhibit a graph with exactly one node of odd
valency then I'll think about it. ;-)

The theorem goes back to Euler's original 1736 article on the
Koenigsberg bridges problem. He proved one half of it but just stated
the converse, which was proved by Hierholzer in 1873. You can read
translations of both the original papers with modern explanations in
Chapter 1 of Biggs, Lloyd & Wilson, "Graph Theory 1736-1936".

Ken Pledger.

[Gerry Myerson]

In article <Ken.Pledger-60F3...@bats.mcs.vuw.ac.nz>,
Ken Pledger <Ken.P...@mcs.vuw.ac.nz> wrote:

> In article <aia501d3n3ml9gfqm...@4ax.com>,
> Steve Gray <ste...@adelphia.net> wrote:
>
> > An obvious threorem in simple graph theory says that no graph with no
> > 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, and a reference would be even nicer.
> > Thanks for any info.
> >
> > Steve Gray
>
>
> Well, if you can exhibit a graph with exactly one node of odd
> valency then I'll think about it. ;-)

Easy: x-----x-----x-----x-----x-----x-----x-----x-----x-----x....

Hey, no one said it had to be a finite graph.

--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

[Timothy Little]

Steve Gray wrote:
> An obvious threorem in simple graph theory says that no graph
> with no 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?

No. Consider the following simple graph:

*---* *
\ / / \
* *---*

All nodes have even order, yet it cannot be drawn in one continuous
path. Obviously such a theorem would have to be restricted to
connected simple graphs. Although we can generalize path to infinite
graphs (e.g. f:N->V or f:Z->V such that (f(x),f(x+1)) in E), we don't
want to allow these sorts of graphs either:

.
.
.
|
*
|
*---*---. . .
|
*
|
.
.
.

It can be proved fairly easily for finite simple connected graphs.

- Tim