Prove that a graph G contains no cycles IF AND ONLY IF the intersection of any two intersecting paths is also a path in G.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
HINT: If there are paths $P_1$ and $P_2$ whose intersection $H$ is not a path, there must be vertices $u,v\in H$ such that $H$ does not contain a path from $u$ to $v$. On the other hand, you know that $P_1$ does contain a path from $u$ to $v$, and $P_2$ contains a path from $v$ to $u$, so ... ?
Showing that if $G$ has a cycle, then it has two paths whose intersection is not a path is very straightforward; the hint for the other direction should be of some help here as well.