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 already.
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.