Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: An Argument for the Subroot Node
Replies: 28   Last Post: Mar 14, 2008 8:32 PM

 Messages: [ Previous | Next ]
 David R Tribble Posts: 3,426 Registered: 7/21/05
Re: An Argument for the Subroot Node
Posted: Mar 14, 2008 6:07 PM

briggs wrote:
>> 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.

>

Tony Orlow wrote:
> Does this say anything about a node with a single edge between it and
> itself? It seems that doesn't quite qualify as a cycle, eh?

Of course it does. There is no need to explicitly mention
or rule out such edges because the rules implicitly do so

A tree with a "root" node containing a path to itself would,
of course, have more than one path between it an any of
its children nodes, i.e., paths that go through the cyclical
link to itself and paths that don't, as per rule 1 above.

Date Subject Author
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 G. Frege
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 G. Frege
3/11/08 J. Antonio Perez M.
3/11/08 G. Frege
3/11/08 G. Frege
3/11/08 Tony Orlow
3/11/08 briggs@encompasserve.org
3/14/08 Tony Orlow
3/14/08 David R Tribble
3/14/08 LudovicoVan
3/11/08 Tony Orlow
3/11/08 J. Antonio Perez M.
3/11/08 Tony Orlow
3/11/08 Tony Orlow
3/11/08 Tony Orlow
3/11/08 LudovicoVan
3/11/08 LudovicoVan
3/14/08 Tony Orlow
3/14/08 LudovicoVan
3/14/08 LudovicoVan
3/11/08 David R Tribble
3/11/08 LudovicoVan
3/11/08 LudovicoVan