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.
Prove the following (graph theory)
1
$\begingroup$
graph-theory
1 Answers
3
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.
-
0@Heisenberg: You’re welcome! – 2012-09-30