1
$\begingroup$

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.

1 Answers 1

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
    Why does P2 necessarily contain a path from v to u?2012-09-30
  • 0
    @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$.2012-09-30
  • 0
    So I'm assuming the only way that P1 and P2 can have paths from u to v and v to u respectively is if H is a cycle containing u and v?2012-09-30
  • 0
    @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.2012-09-30
  • 0
    @Heisenberg: You’re welcome!2012-09-30