Date: Mar 11, 2008 3:36 PM
Author: briggs@encompasserve.org
Subject: Re: An Argument for the Subroot Node
In article <r0bdt314kmk4gc4pkjbau9j6vf4n99r48q@4ax.com>, G. Frege <nomail@invalid> writes:

> On Tue, 11 Mar 2008 16:51:03 +0100, G. Frege <nomail@invalid> wrote:

>

> Oopos... typo/thinko...

>

>>>

>>> According to it, the perimeter of a triangle is a tree...

>>> which, of course, it is not.

>>>

>> Wait a second. If the nodes of your triangle were, say a, b, c then

>> (say) a, b would be connected by more than one path:

>>

>> p_1 = ((a,b))

>>

>> p_2 = ((a,b), (b,c), (c,a), (a,b))

>>

> No?

Why not:

p_3 = ((a,c),(c,b))

Now the example doesn't imply that cycles are the only way to get multiple

paths.

You'd better lay out your definition of "path".

It appears that your current working definition of path is along

the lines of:

An "edge" is an ordered pair of vertexes that are directly connected.

A "path" is a sequence of edges such that the terminal vertex of

each edge in the sequence is the initial vertex of the next edge

(if any) in the sequence. In addition, the initial vertex

of an edge in the sequence may not appear as the terminal vertex

of the next edge in the sequence. (No direct back-tracking).

It seems fairly easy to prove that:

1. If a graph has a cycle, it will have two distinct nodes with

more than one path between them.

2. If a graph has two distinct nodes with more than one path between

them, it will contain a cycle.

3. If a graph is connected, there will be at least one path between

any pair of distinct nodes.

4. If a graph has at least one path between any pair of distinct nodes,

it is connected.