7.33

Idea. In an undirected graph an edge e = {u,v} lies on a cycle iff after deleting it there is still a path between its two endpoints.

Algorithm cycle-through-edge(G, e)
1. Let (u,v) be the endpoints of e.
2. Temporarily remove e from the adjacency lists of u and v (this is O(1)).
3. Run a DFS/BFS starting at u that ignores the removed edge.
4. If v is reached, return “YES – a cycle containing e exists”;
otherwise return “NO”.

cycle_through_edge(G, e=(u,v)): remove e from G visited = DFS(G, start=u) return (v in visited)

Correctness proof (sketch).
• (⇐) If v is still reachable from u without e, concatenate that path with e; the result is a cycle containing e.
• (⇒) If a cycle containing e exists, removing e leaves another path between u and v, so the search must reach v.

Running time. The search touches every vertex and edge at most once, so the overall complexity is Θ(|V| + |E|), i.e. linear. Only O(|V|) extra memory is used for the visited set.

Back to Chapter 7