Graph Theory37 sections · 1633 units
Open in Course

Low-Link Example

Computing values step by step

Graph: 1−21-2, 2−32-3, 3−13-1, 2−42-4. Start DFS at 11. Discovery times: disc[1]=0, disc[2]=1, disc[3]=2, disc[4]=3. Low-link values: low[1]=0 (reaches itself), low[2]=0 (back edge 3−13-1 reaches 11), low[3]=0 (back edge 3−13-1), low[4]=3 (no back edges, dead end).

Edge 2−42-4 is a bridge because low[4]=3 > disc[2]=1. The subtree of 44 cannot reach anything earlier than 44 itself. Removing edge 2−42-4 disconnects node 44 from the rest.