On Existence of Must-Include Paths and Cycles in Undirected Graphs

Given an undirected graph $G=(V,E)$ and vertices s,t,w₁,w₂∈ V, we study the following path existence problem (PEP): does there exist a simple path from s to t containing w₁ and w₂, and the closely related cycle existence problem (CEP) of a simple cycle containing three given graph elements (vertices or edges).We reduce the PEP to the CEP, and the general graph case of the CEP to that of a triconnected graph. We show that two simple necessary conditions for the existence of a cycle containing three given edges in a triconnected graph are sufficient.