Let G be an undirected, simple graph containing distinct vertices x and y. Let P,Q,R be three distinct paths in G from x to y. We can assume the graph G is only those paths (any vertex in G is in one of P,Q, and R and same with any edge in G).
Assume there is no vertex (other than x and y) such that P,Q, and R contain that vertex. Does this guarantee us a cycle which contains both x and y? (The cycle does not have to be simply two of P,Q, and R but may be created by two x-y paths which are made from the union of P,Q, and R).
My feeling is it does, but I am having trouble proving it rigorously.
Mostly I have tried to solve it by starting with the three paths then adjusting the paths so that P and R never touch. Start at x and work towards y, when two paths, say P and Q, intersect at a vertex v we can swap the subpath from v to y of P with the v-y subpath of the Q. But this is tough because it may affect a vertex on P that was closer to x than v.
Another thought was more combinatorial: If we have two x-y paths which intersect each other at a vertex which is not x or y then they do not create a cycle which contains both x and y. So if we start with three paths that have some intersections among them, do these intersections make more paths which would also need to intersect each other for there to be no cycle containing x and y? Seems like the number of paths made by intersections would grow larger than the number of intersections necessary to stop any two x-y paths from forming a cycle, but I am not sure how to concretely show that to be true.
Thanks in advance!
