# Prove the following (graph theory)

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.

-

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.
@Heisenberg: Any path necessarily contains a subpath between any two of its vertices. E.g., the path $v_0v_1\dots v_n$ contains the directed subpaths $v_kv_{k+1}\dots v_m$ and $v_mv_{m-1}\dots v_k$ between $v_k$ and $v_m$, where $0\le k\le m\le n$. – Brian M. Scott Sep 30 '12 at 0:25
@Heisenberg: That's right: you can paste together a path from $u$ to $v$ in $P_1$ and a path from $v$ to $u$ in $P_2$ to get a cycle. – Brian M. Scott Sep 30 '12 at 0:33