In a 2-connected simple graph, is there always a simple cycle containing any given path P and disjoint edge e?

197 Views Asked by At

For any finite simple graph $G$ which is 2-connected, given a path $P$ and a disjoint edge $e$, is it true that there is always a simple cycle containing $P$ and $e$?

If instead of an edge $e$, a vertex $v$ is specified with $v \notin V(P)$, then I believe the answer is yes by Menger's theorem.

2

There are 2 best solutions below

0
On BEST ANSWER

No.

Counterexample

It is also not true of a path and a vertex. Pick the path specified above and one end of the edge specified above.

1
On

No. The path $P$ may contain enough edges to cut the remainder so much apart that its endpoints cannot connect to $e$ any more.