How to Learn Tarjan’s Low-Link Algorithm: DFS Discovery Times, Bridges, Articulation Points and Biconnected Structure

Wait, What?

One depth-first search can reveal the single edges and vertices that hold an entire network together.

At first, bridges and articulation points look like deletion problems. Remove an edge, check whether the graph disconnects. Put it back. Remove a vertex, check again. That works as a definition, but it is a poor algorithm when the graph is large.

Tarjan’s low-link idea turns the problem around. Instead of repeatedly damaging the graph to see what breaks, one depth-first search records how far every subtree can reach back toward earlier vertices. From that information, a bridge or articulation point becomes a local inequality.

For a beginner, this is a lesson about DFS trees. At intermediate level, the key object is the low-link value. At advanced level, the work is proving the bridge and cut-vertex tests. At professional level, the important issues are disconnected graphs, multiedges, recursion depth, edge stacks, differential testing, and deciding whether a static low-link algorithm is even the right tool for a graph that changes continuously.

Quick Answer

Learn Tarjan’s low-link method in this order: connected components → DFS tree edges and back edges → discovery times → define low-link values → compute low values on return from DFS → test bridges with low[child] > disc[parent] → test non-root articulation points with low[child] ≥ disc[parent] → handle the DFS root separately → extend the same machinery to biconnected components → test on multigraphs and disconnected graphs → replace recursion when stack depth is unsafe → validate against brute force and a trusted graph library.

1. The first job: what is a bridge?

In an undirected graph, an edge is a bridge if removing that edge increases the number of connected components.

Imagine two dense clusters connected by one cable. Inside each cluster there may be many alternative routes, but that single cable is the only route between the clusters. The cable is a bridge.

The naive algorithm is obvious:

for each edge e:
    remove e
    count connected components
    restore e

If connectivity itself costs O(V+E), repeating it for every edge is unnecessarily expensive. The low-link method finds all bridges in O(V+E).

2. The second job: what is an articulation point?

A vertex is an articulation point, or cut vertex, if removing the vertex and all incident edges increases the number of connected components.

The definition resembles a bridge, but the test is not identical. One vertex may have several DFS children, and the root of the DFS tree behaves differently from every other vertex.

3. Start with a depth-first-search tree

Run DFS. Each first-time traversal to an unvisited vertex becomes a tree edge. In an undirected graph, an edge to an already discovered ancestor is a back edge.

Assign each vertex a discovery number:

disc[v] = the time DFS first visits v

If DFS visits A, then B, then C, we might have:

disc[A] = 0
disc[B] = 1
disc[C] = 2

Discovery time tells us how early a vertex appears in the DFS ancestry.

4. Low-link values ask a more useful question

For each vertex v, define low[v] as the smallest discovery time reachable from the DFS subtree rooted at v by going down zero or more tree edges and then using at most one back edge.

A practical recurrence is:

low[v] = disc[v]

for each neighbour to of v:
    if to is unvisited:
        DFS(to)
        low[v] = min(low[v], low[to])
    else if edge(v,to) is not the DFS parent edge:
        low[v] = min(low[v], disc[to])

The phrase “parent edge” matters. In a simple graph it is often taught as “ignore the parent vertex,” but a multigraph can have two parallel edges to the same parent. A professional implementation tracks edge identity so that it ignores only the exact tree edge used to enter the child.

5. What low[v] means visually

Suppose vertex v has a child subtree. If some descendant has a back edge to an ancestor discovered at time 2, then the low value of that descendant chain can fall to 2.

A small low value therefore says: “this subtree has an escape route upward.”

A low value that never rises above the parent’s discovery time says something very different: “the subtree can reconnect to the parent or an earlier ancestor without depending entirely on the tree edge.”

6. The bridge test

Suppose DFS used tree edge (v,to). After the recursive search of to is complete:

if low[to] > disc[v]:
    (v,to) is a bridge

Why strictly greater? If low[to] == disc[v], the child subtree has a back edge reaching v itself. That gives another route between the child side and v, so the tree edge is not the only connection.

If low[to] > disc[v], the child subtree cannot reach v or any ancestor of v except through the tree edge. Remove that edge and the subtree is cut off.

7. The articulation-point test for non-root vertices

For a non-root vertex v, if some DFS child to satisfies:

low[to] >= disc[v]

then v is an articulation point.

This time equality is enough. If the child subtree can only climb back as high as v itself, then removing v removes that connection. The subtree cannot bypass v to reach an earlier ancestor.

8. The root is the famous special case

The DFS root has no parent, so the non-root inequality does not characterize it correctly.

The root is an articulation point if and only if it has more than one DFS-tree child.

If the root has two independent DFS children, there was no edge discovered that let one child’s search reach the other before returning to the root. Removing the root separates those child subtrees.

9. A worked example

Consider two triangles joined by one edge:

A ----- B
 \     /
   \ /
    C
    |
    D
   / \
  E---F

More precisely, edges are:

A-B, B-C, C-A,
C-D,
D-E, E-F, F-D

The edge C-D is a bridge. Vertices C and D are articulation points.

If DFS begins at A and reaches A → B → C → D → E → F, the triangle A-B-C creates a back edge that lowers the low values inside the first cluster. The triangle D-E-F does the same inside the second cluster. But nothing in the D-E-F subtree reaches C or an ancestor of C except through C-D.

Therefore, after D’s subtree is complete, low[D] > disc[C]. The inequality exposes the bridge directly.

10. Trace the algorithm, do not memorize it

A useful learning table is:

vertex | parent edge | disc | low | DFS children | bridge test | articulation test

Fill disc when a vertex is first visited. Fill or revise low only when you see a back edge or return from a child.

The key habit is to ask what caused each low value to decrease.

11. The core recursive shape

timer = 0

def dfs(v, parent_edge):
    visited[v] = true
    disc[v] = low[v] = timer
    timer += 1
    children = 0

    for edge e = (v, to):
        if e == parent_edge:
            continue

        if visited[to]:
            low[v] = min(low[v], disc[to])
        else:
            dfs(to, e)
            low[v] = min(low[v], low[to])

            if low[to] > disc[v]:
                report bridge e

            if parent_edge exists and low[to] >= disc[v]:
                mark v articulation

            children += 1

    if parent_edge does not exist and children > 1:
        mark v articulation

This is a conceptual template. Real graph containers may represent undirected edges twice, so edge IDs are often safer than comparing endpoint pairs.

12. Disconnected graphs require a DFS forest

Running DFS once is not enough when the graph is disconnected.

for v in vertices:
    if not visited[v]:
        dfs(v, no_parent_edge)

Each new DFS root gets its own root-child articulation rule. Bridges and articulation points are defined relative to the whole graph, but they are discovered component by component.

13. Why parent-vertex logic fails on parallel edges

Suppose vertices U and V are connected by two parallel edges. Neither edge is a bridge because removing one still leaves the other.

If the DFS enters V from U and the implementation ignores every edge back to U merely because U is the parent vertex, it will miss the second parallel edge. Then low[V] may remain too high and the algorithm can incorrectly report the tree edge as a bridge.

The professional rule is: ignore the exact parent edge, not all edges to the parent endpoint.

14. Self-loops do not create bridges

A self-loop connects a vertex to itself. Removing it cannot disconnect two previously connected regions. It may appear in the adjacency structure and should not corrupt low-link updates.

Test self-loops explicitly rather than assuming input data is simple.

15. Biconnected components come from the same evidence

A biconnected component is a maximal subgraph that remains connected after removing any single vertex from that component.

Tarjan-style algorithms can recover edge-biconnected or vertex-biconnected structure by maintaining additional state, often an edge stack. When DFS finishes a child to with low[to] ≥ disc[v], the edges accumulated since the corresponding tree edge form one biconnected block.

This is powerful because bridges, articulation points and biconnected decomposition are not three unrelated tricks. They are different readings of the same DFS ancestry information.

16. Complexity is linear

With adjacency lists, each vertex is discovered once and each undirected edge is examined a constant number of times.

The time complexity is:

O(V + E)

The extra working memory is O(V), excluding the graph itself, plus an O(E) edge stack if full biconnected-component extraction is required.

17. Recursion depth is an engineering decision

A path graph with millions of vertices can drive recursive DFS millions of calls deep. The algorithm is still theoretically linear, but the process may crash from stack exhaustion.

Production choices include:

• an explicit iterative DFS stack;
• a runtime with safely expandable stacks;
• input-size guards;
• carefully controlled recursion limits only when justified.

Changing the stack mechanism must preserve the moment at which child low values are propagated back to parents. That return-time ordering is the heart of the recurrence.

18. Iterative DFS needs two kinds of events

A naive iterative DFS that only pushes vertices can lose the “after child returns” moment needed for low[parent] = min(low[parent], low[child]).

A robust iterative design stores a frame with the vertex, parent edge, next adjacency index and child count, or emits explicit ENTER and EXIT events.

When the child frame exits, the parent frame performs the same work the recursive call would have performed after return.

19. Do not confuse low-link values across algorithms

Tarjan’s strongly connected components algorithm for directed graphs also uses values commonly called low or lowlink, but the exact semantics and stack conditions differ.

For undirected bridges and articulation points, the relevant information is the earliest DFS ancestor reachable from a subtree through tree edges plus a back edge. For directed SCCs, membership in the active DFS stack changes the update rules.

Names are not contracts. Learn the invariant for the specific algorithm.

20. A strong teaching sequence: predict → trace → explain → modify → build

Programming-education research supports reducing unnecessary search for novices by beginning with worked examples and making procedural subgoals visible. A useful lesson sequence is:

• Predict: circle the edge or vertex you think will disconnect a small graph.
• Trace: fill discovery and low values on a supplied DFS tree.
• Explain: say why > is used for bridges but ≥ is used for non-root articulation points.
• Modify: add one back edge and predict which bridge disappears.
• Build: implement the algorithm only after the inequalities make sense.

This follows the same broad logic as PRIMM—Predict, Run, Investigate, Modify, Make—and subgoal-labeled worked examples: understand the procedure before being asked to invent it from a blank editor.

21. The bridge inequality should be explainable in words

A learner has not fully understood low[child] > disc[parent] if they can only reproduce the symbols.

The verbal explanation is: “the child subtree cannot reach the parent or any earlier ancestor without using this tree edge.”

That sentence is the proof idea.

22. The articulation inequality should also be explainable in words

For a non-root vertex, low[child] ≥ disc[v] means: “the child subtree cannot bypass v to reach an ancestor of v.”

If v disappears, that subtree loses its route to the earlier part of the DFS tree.

23. Test against a brute-force oracle

For small random graphs, write a slow but obviously correct checker.

For each edge:

1. count connected components;
2. remove the edge;
3. count again;
4. restore it;
5. compare the result with the low-link algorithm.

For each vertex, do the analogous deletion test.

This kind of differential testing is far more convincing than checking a few hand-picked examples.

24. Include adversarial graph families

Your tests should include:

• single vertices and empty graphs;
• single edges;
• long paths, where every edge is a bridge;
• cycles, where no edge is a bridge;
• stars, where the center is an articulation point;
• complete graphs;
• disconnected unions;
• parallel edges;
• self-loops;
• graphs with multiple biconnected blocks sharing articulation points.

25. Useful runtime invariants

• low[v] ≤ disc[v] after DFS completion.
• Every tree child is processed exactly once.
• Discovery times are unique within one DFS forest.
• A reported bridge must be a tree edge.
• The root articulation rule depends on DFS children, not raw graph degree.
• In a multigraph, only the exact parent edge is skipped.

26. Validate with mature libraries

NetworkX documents non-recursive DFS-based articulation-point and biconnected-component routines. Boost Graph Library exposes biconnected components and articulation points with explicit discovery-time and low-point maps. These are useful independent references when validating semantics and edge cases.

Do not copy library output blindly. Use it as a differential oracle while retaining your own invariants and small proof cases.

27. Where professionals use this structure

Low-link decomposition appears in network reliability, infrastructure dependency analysis, circuit and communication topology, graph preprocessing, vulnerability detection, compiler and program-analysis structures, and many algorithms that need a block-cut decomposition.

The algorithm answers a structural question: where does the graph have only one route through an edge or one mandatory passage through a vertex?

28. Static low-link analysis is not dynamic connectivity

If edges are inserted and deleted continuously, rerunning O(V+E) DFS after every update may be too expensive.

Dynamic connectivity, dynamic bridges and dynamic biconnectivity require different machinery. The professional skill is recognizing that a beautiful static linear-time algorithm may still be the wrong operational tool for a high-update workload.

29. Common failure states

• Using low[child] ≥ disc[parent] for bridges instead of strict >.
• Using the non-root articulation rule on the DFS root.
• Counting root graph degree instead of root DFS children.
• Updating low[v] with low[to] for an already visited back-edge endpoint instead of disc[to].
• Ignoring every edge to the parent vertex in a multigraph.
• Running DFS from only one start vertex in a disconnected graph.
• Recursing beyond safe stack depth.
• Confusing undirected low-link semantics with Tarjan SCC low-link semantics.

30. Beginner-to-professional learning ladder

• Beginner: identify bridges and articulation points by inspection and trace DFS discovery order.
• Foundation: calculate low values on small DFS trees.
• Intermediate: implement bridges and cut vertices for simple undirected graphs.
• Advanced: prove the inequalities, handle disconnected graphs, and extract biconnected components.
• Professional: support multigraph edge IDs, iterative DFS, stack-safe execution, brute-force differential testing, library cross-checks and clear static-versus-dynamic workload boundaries.

31. Ownership boundary

This article owns the public learning job for Tarjan-style low-link reasoning in undirected graphs: discovery times, low values, bridges, articulation points and biconnected structure. It does not redefine general graph-algorithm foundations, strongly connected components, learner-state systems, assessment calibration, studying interfaces or any private implementation machinery elsewhere in the eduKate ecosystem.

Sources and further reading

• Robert Tarjan, “Depth-First Search and Linear Graph Algorithms,” SIAM Journal on Computing, 1972: SIAM.
• John Hopcroft and Robert Tarjan, “Efficient Algorithms for Graph Manipulation,” Communications of the ACM, 1973: DOI.
• NetworkX, current articulation-points documentation: NetworkX.
• Boost Graph Library, current biconnected-components and articulation-points documentation: Boost.
• ACM/IEEE-CS/AAAI CS2023, Algorithms and Complexity knowledge area: CS2023.
• Computer Science Teachers Association, 2026 standards overview emphasizing algorithms, reading, evaluating, modifying and debugging programs: CSTA.
• Sentance, Waite and Kallia, PRIMM programming pedagogy: SIGCSE.
• Margulieux, Morrison and Decker, subgoal-labeled worked examples in introductory programming: International Journal of STEM Education.

Professional rule: you understand low-link algorithms when you can look at a child subtree and explain, in plain language, exactly what route would have to exist for a bridge or articulation point to disappear.