Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 68 ยท Graph Theory

Paths, Cycles and Connectivity

Learn walks, paths, cycles, connected components and cut vertices, and compute each one in Python with BFS, DFS and matrix powers.

Most questions about a graph are really questions about getting from one vertex to another. Can a message travel from one computer to another? Are two users in the same friend circle? If a single road closes, is the country split in two? The vocabulary of walks, paths, cycles and connectivity answers these precisely.

This lesson defines those terms, shows how a traversal decides whether two vertices are connected, and finds the weak points of a network: cut vertices and bridges. If you want the engineering side of the same traversals, see Graph BFS, Graph DFS and Graph Components. Here we focus on what the traversals prove.

Moving through a graph

Walk Any sequence of edges. Repeats allowed.
Path A walk that never repeats a vertex.
Cycle A path that returns to its start.
1 / 2

Walks, paths and cycles

Fix an undirected graph. A walk from u to v is a sequence of vertices u = v0, v1, ..., vk = v in which each consecutive pair is an edge. Its length is the number of edges, k. Walks may revisit vertices and reuse edges.

  • A trail is a walk with no repeated edge.
  • A path is a walk with no repeated vertex.
  • A closed walk starts and ends at the same vertex.
  • A cycle is a closed walk of length at least 3 in which the only repeated vertex is the start and end. In other words, a path whose two ends are joined by an edge.

A useful fact: if there is a walk from u to v, there is also a path. Whenever a walk repeats a vertex, cut out the loop between the two visits; what remains is shorter, and you can repeat until nothing repeats. So reachability can be decided by looking for paths only.

The distance between two vertices is the length of a shortest path between them (infinity if none exists). The largest distance in the graph is its diameter.

Counting walks with matrix powers

Here is a neat link back to the adjacency matrix from Graphs: Terms and Representations. If A is the adjacency matrix, the entry (A^k)[i][j] is the number of walks of length exactly k from vertex i to vertex j. For k = 1 that is just the edge indicator. For k = 2, a walk i, x, j exists for every common neighbor x, and the matrix product adds up one term per x.

Python Counting walks with powers of the adjacency matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The diagonal of A^3 counts closed walks of length 3, which in a simple graph are exactly triangles traversed in either direction. That is a quick way to count triangles: sum the diagonal of A^3 and divide by 6.

Connectivity and components

An undirected graph is connected if every pair of vertices is joined by a path. Otherwise it splits into connected components: maximal groups of vertices that can all reach one another, with no edges between groups. "Being reachable from" is an equivalence relation (reflexive, symmetric, transitive), and the components are exactly its equivalence classes.

How do we find them? Start anywhere and explore. Breadth-first search (BFS) visits vertices in order of distance, using a queue; depth-first search (DFS) dives along one branch before backing up, using a stack or recursion. Either one visits precisely the set of vertices reachable from the start. That set is the component, and if it is smaller than the whole graph the graph is disconnected. A traversal is therefore not just a search routine but a proof of connectivity: the sequence of discovery edges is an actual path to every vertex found.

Counting edges gives a hard limit. A connected graph on n vertices has at least n - 1 edges (trees reach this minimum, see Trees and Spanning Trees), and a graph with at most n - 2 edges cannot be connected.

Python Connected components and shortest paths with BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The BFS parent pointers give a shortest path because BFS discovers vertices in order of distance. Joining the three components needs just two more edges, one per gap.

Distance, eccentricity, radius, diameter and center

How "wide" is a network? Start with distance. In a connected graph, d(u, v) is the number of edges on a shortest path from u to v, which breadth-first search finds in one pass. From that single idea come four standard measurements.

  • The eccentricity ecc(v) of a vertex is its distance to the farthest vertex: max over u of d(v, u).
  • The radius is the smallest eccentricity, and the diameter is the largest.
  • The center is the set of vertices whose eccentricity equals the radius (the "most central" vertices). The periphery is the set whose eccentricity equals the diameter.

Two facts help you sanity-check an answer: radius โ‰ค diameter โ‰ค 2 ยท radius, and a tree has either one or two central vertices. For a path on 7 vertices the center is the middle vertex, a star's center is its hub, and every vertex of a cycle is central (all eccentricities are equal).

These numbers are practical. The diameter bounds the worst-case number of hops in a network, and the center is the best place to put a server if you want to minimize the longest trip to any client.

Python Eccentricity, radius, diameter, center and periphery via BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The even path has two central vertices, which is the typical tree behavior. In the small network, b, c and e form the center, while the end of the tail (a) and the far side of the cycle (d, f) form the periphery.

Cut vertices and bridges

Connected does not mean robust. A cut vertex (articulation point) is a vertex whose removal, together with its edges, leaves the graph with more components. A bridge is an edge with the same property. They mark single points of failure: the only router linking two offices, or the only road to an island.

A simple, always-correct way to find them is brute force: delete each vertex (or edge) in turn and count components again. Faster one-pass algorithms exist (they use DFS discovery times and "low" values, see Graph Components), but the brute-force version follows the definition and is perfect for small graphs.

Python Finding cut vertices and bridges by definition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two triangles are joined by the single link c-d. That edge is the only bridge, and both of its endpoints are cut vertices. Inside a triangle no edge is a bridge, because every edge lies on a cycle. That is a general rule: an edge is a bridge exactly when it lies on no cycle.

Tarjan's algorithm: bridges and cut vertices in one pass

Brute force deletes each vertex or edge and recounts components, which takes O(V ยท (V + E)). Tarjan's algorithm finds every bridge and cut vertex in a single depth-first search, in O(V + E).

The idea uses two numbers per vertex v:

  • disc[v]: the discovery time, the order in which DFS first reaches v.
  • low[v]: the smallest discovery time reachable from the subtree of v using tree edges downward and at most one back edge upward.

DFS on an undirected graph produces tree edges and back edges (edges to an ancestor). Consider a tree edge u โ†’ v where v is the child:

  • Bridge: if low[v] > disc[u], nothing in the subtree of v can climb back to u or above, so removing u-v disconnects the subtree. The edge is a bridge.
  • Cut vertex: if low[v] โ‰ฅ disc[u] for some child v, the subtree of v can only escape through u itself, so removing u separates it. The root is a special case: it is a cut vertex only if it has two or more DFS children.

Recursive DFS can overflow the stack on a long path, so the version below is iterative with an explicit stack, and it ignores the single edge back to the parent (parallel edges would need edge ids, which we skip because the graphs are simple).

Python Iterative Tarjan, checked against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute-force version is the definition; Tarjan's version is the same answer for a tiny fraction of the work. In the checks, components counts the components among the remaining vertices, so deleting an isolated vertex never counts as a cut.

Keep the two numbers straight: disc says when DFS arrived, and low says how far up the subtree can climb with a single back edge. A bridge needs a strict inequality (low[v] > disc[u]) because a back edge to u itself would put the edge on a cycle, while a cut vertex allows equality (low[v] >= disc[u]) because returning to u still passes through the vertex being removed.

Directed graphs in one paragraph

With arrows, reachability is not symmetric. A directed graph is strongly connected if every vertex can reach every other following arrows, and weakly connected if it becomes connected after ignoring directions. The maximal strongly connected pieces are the strongly connected components. A directed graph with no directed cycle is a DAG, the structure behind task ordering (see Topological Sort).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the difference between a walk and a path?

    A walk is any sequence of adjacent vertices, so it can revisit vertices and edges. A path never repeats a vertex.
  2. 2. A graph has 10 vertices and 7 edges. Which statement must be true?

    A connected graph on 10 vertices needs at least 9 edges. With only 7 it cannot be connected. It may have more than 3 components, and it need not contain a cycle.
  3. 3. Which edge is a bridge?

    If an edge lies on a cycle, the rest of the cycle still connects its endpoints after removal. A bridge is exactly an edge on no cycle.
  4. 4. If A is the adjacency matrix of a graph, what does the entry (A^3)[i][j] count?

    Matrix powers count walks, not paths: the walks may revisit vertices, for example i, j, i, j.
  5. 5. Why does BFS from a vertex find exactly its connected component?

    BFS keeps following edges to unseen neighbors, so it reaches every vertex joined to the start by a path and nothing else.

Summary

  • A walk is a sequence of adjacent vertices, a trail repeats no edge, a path repeats no vertex, and a cycle is a closed path of length at least 3.
  • If any walk joins two vertices, a path does too; distance is the length of a shortest path.
  • (A^k)[i][j] counts walks of length k; the trace of A^3 divided by 6 counts triangles.
  • A graph is connected if all pairs are joined by paths; otherwise it splits into components, which BFS or DFS finds one at a time. Connected needs at least n - 1 edges.
  • Cut vertices and bridges are single points of failure; a bridge is exactly an edge on no cycle.

Next: Euler and Hamilton Paths, which ask for walks that use every edge or every vertex.