given a directed graph (can have cycles) with:
- an arbitrary number of nodes
- an arbitrary number of edges
- that satisfies the condition that there is (at least) one trail (i.e. a walk where no edge is repeated) that visits all nodes.
Would this be a true statement:
Every trail (again, can not repeat edges) from a given starting node will have the same ending node. This could be either an open walk (start and end nodes differ) or a closed walk (start and end nodes are the same). However, the walk must satisfy the condition that it cannot end until there are no available edges to continue walking on.
Note that even though the same edge cannot be walked more than once, nodes may be visited multiple times. I know this may not satisfy the definition of "trail", but it fits the problem I have.
Examples:
trivial case: the graph A->B, B->A. Given A as a start node, the end node is always A.
slightly more complex example:
Given A as start node, C is the end node.
Is there a counterproof where there are two trails (open or closed) that ends in different nodes? Or, conversely, is there a proof/name for this graph property?
Disclaimer: I'm not very experienced in math or graph theory, this is a problem that I encountered while programming.
Best Answer
Remove the edge from $B$ to $A$ in your second graph. Then from $A$ you have trails
$$A\to B\to C\to B$$
and
$$A\to C\to B\to C\;.$$
I am assuming here that the edge $B\to C$ is considered different from the edge $C\to B$, but if that is not the case, this is still a counterexample.