Every closed walk in a tree uses at least one of its edges at least twice.

786 Views Asked by At

Assume every closed walk in a connected graph $G$ uses all of its edges at least twice. Then $G$ must be a tree.

How do I prove this statement? I am using the fact that there is a unique path between any two distinct vertices in a tree. If a closed walk begins and ends on $u$ and traverses the edge between $v$ and $w$, I know it must traverse $v$ in both the $uw$-path and $wu$-path. But how can I prove the statement holds if the walk does not take a direct path from vertex $w$ to vertex $u$?

1

There are 1 best solutions below

2
On BEST ANSWER

A closed path is a cycle iff it has no repeated edges. But a tree is exactly an acyclic, connected graph, and since $G$ is assumed connected and we have shown acyclic is equivalent to every closed path having no repeated edges, we are done.


If you have never seen the proof that "unique path" iff acyclic and connected (i.e. trees are exactly the acyclic connected graphs) the proof is easy:

If $G$ has a unique path between two points, in particular it has a path and so $G$ is connected. Further if there were a cycle, $C$, let $v_1\ne v_2$ be distinct verticles in the cycle and let $\gamma_1$ be the path from $v_1$ to $v_2$ along $C$ and $\gamma_2$ be the path from $v_2$ back to $v_1$ along the rest of $C$. Then $\gamma_2^{-1}$ is a distinct path from $v_1$ to $v_2$ from $\gamma_1$, hence contradicting the uniqueness.

Conversely if $G$ is acyclic and connected there is a path between any two points. If by way of contradiction there were two distinct paths between two points, $\gamma_1,\gamma_2$ then traversing $\gamma_1$ from $v_1$ to $v_2$ and $\gamma_2^{-1}$ (i.e. $\gamma_2$ backwards) from $v_2$ to $v_1$ gives a cycle.