4
$\begingroup$

I think that the proof is easy assuming that there are at least two paths between any two nodes. If that is true then there must be a cycle somewhere. But if there is a cycle then this is not a tree, which is a contradiction. I feel like the step when i say that there must be a cycle if there is more than one path is kind of sloppy. It sounds like it is true but i am not sure about that. How do i make my proof a little bit more rigorous?

$\endgroup$
1
$\begingroup$

If you have two distinct paths between two common nodes, then the paths may agree for a while beginning at the start node, and also agree for a while ending at the end node, but the point is that somewhere the two paths must diverge from each other and be disjoint (even if it's just for one node), and then later return to a common node. If this were not true, you would have the same path for both paths. This gives you your cycle. If you'd like, I can also provide a proof by induction, if you accept that a tree with $n$ nodes is always obtainable somehow by removing a leaf node from a tree with $n+1$ nodes.

$\endgroup$
0
$\begingroup$

Let the least path from node $a$ to node $b$ be edges $x_1...x_m$. If there exists another least path from $a$ to $b$ $y_1...y_n$, then $$x_1...x_ny_n^{-1}...y_1^{-1}$$ is a cycle unless $x_k=y_k$ for all $k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.