Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 68 ยท Graph Theory

Trails, Circuits and Graph Connectivity: kappa, lambda and Menger

Classify walks, trails, paths, circuits and cycles, then measure how well connected a graph is with vertex connectivity, edge connectivity, Whitney's inequality and Menger's theorem.

Paths and Connectivity asked whether a graph is connected at all. A yes-or-no answer is not enough for real networks. Two connected networks can differ hugely: one breaks if a single router dies, the other survives three failures. This lesson first pins down the vocabulary of walks, trails and circuits (a favourite source of exam questions), then measures how connected a graph is.

Walks, trails, paths, circuits and cycles

All of these are sequences of vertices in which consecutive vertices are joined by an edge. They differ in what may repeat and whether the sequence closes.

Name Vertices may repeat? Edges may repeat? Closed?
Walk yes yes maybe
Open walk yes yes no (start differs from end)
Closed walk yes yes yes
Trail (open trail) yes no no
Circuit (closed trail) yes no yes
Path no no no
Cycle only start = end no yes

Every path is a trail, and every trail is a walk, but not the other way round. In a graph with edges 1-2, 2-3, 3-1, 3-4, 4-5, 5-3, the sequence 1, 2, 3, 4, 5, 3, 1 is a closed trail (a circuit): it returns to vertex 1, repeats vertex 3, and uses no edge twice. It is not a cycle, because vertex 3 repeats.

Python Classify a vertex sequence

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.

Cut vertices, bridges and separating sets

A vertex cut (separating set) is a set of vertices whose removal, together with their edges, leaves the graph disconnected. A single-vertex cut is a cut vertex. An edge cut is a set of edges whose removal disconnects the graph; a single-edge cut is a bridge. You met these in the lesson on paths and connectivity; now the size of the smallest cut becomes the measure.

  • The vertex connectivity kappa(G) is the minimum number of vertices whose removal disconnects the graph. For the complete graph K_n, where removal never disconnects it, the convention is kappa(K_n) = n - 1. A disconnected graph has kappa = 0.
  • The edge connectivity lambda(G) is the minimum number of edges whose removal disconnects the graph.
  • A graph is k-connected if kappa(G) >= k (and has more than k vertices), and k-edge-connected if lambda(G) >= k.
  • The minimum degree delta(G) is the smallest vertex degree.

Whitney's inequality ties them together:

Text
kappa(G)  <=  lambda(G)  <=  delta(G)

Why? Deleting all edges at a smallest-degree vertex isolates it, so lambda <= delta. And any edge cut can be converted to a vertex cut of no larger size by choosing one endpoint of each cut edge, so kappa <= lambda. The inequalities can be strict, as the "bowtie" example below shows.

Python Compute kappa, lambda and delta by 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.

You can read the results off the shapes. A path has a cut vertex and a bridge, so kappa = lambda = 1. A cycle needs two removals: 2 and 2. K5 has 4 and 4. The bowtie (two triangles sharing vertex 0) has one cut vertex, so kappa = 1, but you must remove two edges to separate it, so lambda = 2 = delta. The cube and Petersen graph are 3-connected (3, 3, 3): they survive any two failures.

Menger's theorem

Menger's theorem links cuts with paths, and it is one of the central results of graph theory.

For two non-adjacent vertices s and t, the minimum number of vertices whose removal separates s from t equals the maximum number of internally vertex-disjoint paths from s to t.

There is an edge version too: the minimum number of edges separating s from t equals the maximum number of edge-disjoint s-t paths. A global consequence: a graph is k-connected exactly when every pair of vertices is joined by at least k internally disjoint paths. That is the precise sense in which "more connected" means "more independent routes".

Menger's theorem is a special case of the max-flow min-cut theorem (see Shortest Paths and Flows), so you can compute the disjoint-path count with a flow algorithm. Splitting each vertex into an "in" node and an "out" node joined by a capacity-1 edge turns vertex-disjointness into an edge capacity.

Python Menger's theorem: disjoint paths equal the smallest separator

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.

For the Petersen graph every non-adjacent pair is joined by exactly 3 internally disjoint paths and separated by 3 vertices, in agreement with kappa = 3.

Why connectivity matters

  • Networks: kappa is the number of nodes that can fail before the network splits, and lambda is the number of cables. Data-center fabrics and hypercube interconnects are designed to have high kappa.
  • Hypercubes: the d-dimensional cube Q_d has kappa = lambda = delta = d, so it is maximally connected for its degree.
  • Complete bipartite graphs: K_{m,n} has kappa = lambda = min(m, n).
  • Reliability and routing: disjoint paths are the basis of multipath routing and fault-tolerant design.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A walk in which no edge is repeated and which starts and ends at the same vertex is called:

    A trail repeats no edge; a closed trail, which returns to its start, is a circuit. Vertices may still repeat.
  2. 2. What is the vertex connectivity of the complete graph K6?

    By convention kappa(K_n) = n - 1, so 5. You cannot disconnect a complete graph by removing vertices until one vertex is left.
  3. 3. Which inequality does Whitney's theorem state?

    Vertex connectivity is at most edge connectivity, which is at most the minimum degree.
  4. 4. Menger's theorem says that for non-adjacent s and t, the largest number of internally vertex-disjoint s-t paths equals:

    Disjoint paths and minimum separators are dual: the maximum of one equals the minimum of the other.
  5. 5. Two triangles share one vertex (the 'bowtie'). What are kappa and lambda?

    Removing the shared vertex disconnects the graph (kappa = 1), but two edges must be removed to separate it by edges (lambda = 2 = delta).

Summary

  • Walks may repeat anything; trails repeat no edge; paths repeat no vertex; a closed trail is a circuit and a closed path of length 3 or more is a cycle.
  • kappa(G) is the fewest vertices, and lambda(G) the fewest edges, whose removal disconnects the graph.
  • Whitney: kappa <= lambda <= delta, and each can be strictly smaller than the next.
  • Menger: the number of internally disjoint s-t paths equals the size of the smallest s-t separator, so k-connected means every pair has k independent routes.
  • High connectivity means fault tolerance in networks.

Next: Eulerian and Hamiltonian Graphs.