Connectivity and Edge-Connectivity

The question

Eight routers, numbered $0$ to $7$, and fourteen cables. Routers $0$–$3$ are all wired to each other, and so are $4$–$7$. Router $3$ has two more cables, to $4$ and to $5$:

Every router has at least three cables. Does that mean the network survives any two failures? No. If the two cables $3$–$4$ and $3$–$5$ fail, the left group can no longer reach the right group. Worse, one router failure is enough: if router $3$ fails, the same split happens.

So there are two different questions, with two different answers. How many routers must fail before the network splits (here, 1)? How many cables (here, 2)? And how do both compare with the smallest number of cables at any one router (here, 3)? This module defines the two numbers, proves how they are ordered, and shows that each comparison can be strict.

The naive approach, and where it wastes work

A computer can answer both questions by trying every set of routers, then every set of cables, smallest first, until one disconnects the network:

from itertools import combinations
from collections import deque

def network(edges):
    g = {}
    for u, v in edges:
        g.setdefault(u, set()).add(v)
        g.setdefault(v, set()).add(u)
    return g

def connected(g, removed_vertices=(), removed_edges=()):
    """Is what remains of g connected? (One vertex or none counts as connected.)"""
    gone = set(removed_vertices)
    cut = {frozenset(e) for e in removed_edges}
    left = [v for v in g if v not in gone]
    if len(left) <= 1:
        return True
    seen, queue = {left[0]}, deque([left[0]])
    while queue:
        u = queue.popleft()
        for w in g[u]:
            if w not in gone and w not in seen and frozenset((u, w)) not in cut:
                seen.add(w)
                queue.append(w)
    return len(seen) == len(left)

def edges_of(g):
    return sorted({tuple(sorted((u, v))) for u in g for v in g[u]})

def kappa(g):
    """Fewest vertices whose removal disconnects g; n - 1 for a complete graph (by brute force)."""
    n = len(g)
    if all(len(g[v]) == n - 1 for v in g):
        return n - 1
    return next(k for k in range(n) for S in combinations(sorted(g), k) if not connected(g, S))

def kappa_edges(g):
    """Fewest edges whose removal disconnects g (by brute force over edge sets)."""
    E = edges_of(g)
    return next(k for k in range(len(E) + 1) for F in combinations(E, k) if not connected(g, (), F))

K4_left = list(combinations(range(4), 2))
K4_right = [(a + 4, b + 4) for a, b in K4_left]
N = network(K4_left + K4_right + [(3, 4), (3, 5)])
assert len(edges_of(N)) == 14 and min(len(N[v]) for v in N) == 3
assert kappa(N) == 1 and kappa_edges(N) == 2

That is fine for fourteen cables, but the number of cable sets grows like $2^m$. And it proves nothing a reader can check without rerunning it. The rest of the module replaces "try everything" with definitions you can reason about and short evidence: a set of routers or cables whose removal visibly splits the network.

Two numbers, defined carefully

Let $G$ be a graph with $n$ vertices.

• A separating set (or vertex cut) is a set $S$ of vertices such that $G-S$ has more than one component. The connectivity $\kappa (G)$ is the minimum size of a separating set. A complete graph $K_n$ has no separating set at all, since deleting vertices always leaves a complete graph, so by convention $\kappa (K_n)=n-1$ (delete all but one vertex). A disconnected graph has $\kappa =0$: the empty set already separates it.
• $G$ is $k$-connected if $\kappa (G)\ge k$. This is an inequality: a 3-connected graph is also 2-connected. "Connected" is the same as 1-connected for $n\ge 2$.
• A disconnecting set of edges is a set $F$ such that $G-F$ has more than one component. The edge-connectivity ${\kappa }^{\prime }(G)$ is the minimum size of a disconnecting set, and $G$ is $k$-edge-connected if ${\kappa }^{\prime }(G)\ge k$. A disconnected graph has ${\kappa }^{\prime }=0$, and by convention so does the one-vertex graph $K_1$, which no edge set can disconnect.
• For a nonempty proper subset $S$ of the vertices, write $\overline{S}$ for the rest, and $[S,\overline{S}]$ for the set of edges with one end in $S$ and the other in $\overline{S}$. A set of this form is an edge cut.
• A cut vertex is a vertex whose deletion increases the number of components, and a cut edge is an edge with the same property.

Two words are easy to blur, so this course keeps them apart: a disconnecting set is minimum if no disconnecting set has fewer edges, and minimal if no proper subset of it disconnects.

Edge cuts are enough

An edge cut always disconnects: in $G-[S,\overline{S}]$ no edge joins $S$ to $\overline{S}$, and both are nonempty. The converse is the useful direction.

Lemma. In every graph, every disconnecting set $F$ contains an edge cut. If $F$ is a minimal disconnecting set, it is an edge cut.

Proof. $G-F$ is disconnected; let $S$ be the vertex set of one of its components. Then $S$ is nonempty, and $\overline{S}$ is nonempty because $G-F$ has another component. An edge of $G$ from $S$ to $\overline{S}$ cannot survive in $G-F$, or its end in $\overline{S}$ would belong to the component $S$. So $[S,\overline{S}]\subseteq F$. If $F$ is minimal, then $[S,\overline{S}]$, being itself a disconnecting subset of $F$, must equal $F$. $◻$

So ${\kappa }^{\prime }(G)$ is the smallest $|[S,\overline{S}]|$ over nonempty proper subsets $S$: a search over sets of vertices instead of sets of edges. In $N$ the smallest edge cut is $[S,\overline{S}]$ with $S=\{0,1,2,3\}$, the two cables $3$–$4$ and $3$–$5$.

Cut edges are the edges on no cycle

Proposition. An edge $e=uv$ of $G$ is a cut edge if and only if $e$ lies on no cycle of $G$.

Proof. First, $e$ is a cut edge exactly when $G-e$ has no $u,v$-path. If $G-e$ has a $u,v$-path, every walk that used $e$ can detour along it, so no two vertices are separated and the number of components stays the same. If it has none, $u$ and $v$, which were in one component of $G$, lie in different components of $G-e$, so the number of components grows. If $e$ lies on a cycle, the rest of the cycle is a $u,v$-path in $G-e$, so $e$ is not a cut edge. Conversely, if $G-e$ has a $u,v$-path $P$, then $P$ together with $e$ is a cycle through $e$. $◻$

In $N$ every cable lies on a triangle, including $3$–$4$ (on the triangle $3,4,5$), so $N$ has no cut edge, even though router $3$ is a cut vertex:

assert [e for e in edges_of(N) if not connected(N, (), [e])] == []
assert [v for v in N if not connected(N, [v])] == [3]

Whitney's inequality, traced on N

The right half is one line: the edges at a vertex of minimum degree form a disconnecting set (when $G$ has another vertex), so ${\kappa }^{\prime }\le \delta$. The left half needs an idea. Here it is on $N$.

Start from the minimum edge cut $F=[X,Y]$ with $X=\{0,1,2,3\}$ and $Y=\{4,5,6,7\}$. Pick $x\in X$ and $y\in Y$ that are not adjacent: $x=0$, $y=4$. Now collect a set $T$ of vertices:

• every neighbor of $x$ inside $Y$ (router $0$ has none);
• every vertex of $X$ other than $x$ that has a neighbor in $Y$ (only router $3$).

So $T=\{3\}$, and deleting it separates $0$ from $4$:

X, Y = {0, 1, 2, 3}, {4, 5, 6, 7}
F = [(u, v) for u in sorted(X) for v in sorted(N[u]) if v in Y]
T = {3}                                    # the two rules above, applied by hand
assert F == [(3, 4), (3, 5)] and 4 not in N[0]
assert not connected(N, T) and len(T) <= len(F)

Proof of $\kappa (G)\le {\kappa }^{\prime }(G)$. If $G$ has one vertex, both sides are 0 by the conventions. Otherwise let $F$ be a minimum disconnecting set; by the lemma it is an edge cut $[X,Y]$, with $|F|={\kappa }^{\prime }(G)$.

Case 1: every vertex of $X$ is adjacent to every vertex of $Y$. Then

$$|F|=|X||Y|\ge |X|+|Y|-1=n-1\ge \kappa (G).$$

(The middle inequality is $(|X|-1)(|Y|-1)\ge 0$. And $\kappa (G)\le n-1$ for every graph: for $K_n$ by the convention, and otherwise deleting all vertices but two non-adjacent ones separates them.)

Case 2: some $x\in X$ and $y\in Y$ are not adjacent. Let $T$ consist of the neighbors of $x$ in $Y$ together with the vertices of $X-\{x\}$ that have a neighbor in $Y$.

1. $T$ separates $x$ from $y$. Neither $x$ nor $y$ is in $T$: $x\notin X-\{x\}$ and $x\notin Y$, and $y$ is not a neighbor of $x$. An $x,y$-path must use an edge of $F$ to leave $X$. If that first such edge leaves from $x$ itself, its other end is a neighbor of $x$ in $Y$, which is in $T$. Otherwise it leaves from some $x^{\prime }\in X-\{x\}$ with a neighbor in $Y$, and $x^{\prime }\in T$. Either way the path meets $T$.
2. $|T|\le |F|$. Charge each vertex of $T$ to an edge of $F$: a neighbor $y^{\prime }$ of $x$ in $Y$ to the edge $x{y}^{\prime }$, and a vertex $x^{\prime }\in X-\{x\}$ to one of its edges into $Y$. Different vertices get different edges: an edge charged by the first rule has its $X$ end equal to $x$, an edge charged by the second has its $X$ end equal to some $x^{\prime }\ne x$, and within each rule the charged edge determines the vertex.

So $T$ is a separating set with $|T|\le |F|$, and $\kappa (G)\le |T|\le {\kappa }^{\prime }(G)$. $◻$

Proof moves used here. The same moves recur all semester:

• Extremal choice. To bound $\kappa$ by ${\kappa }^{\prime }$, start from a minimum edge cut and convert it into a vertex cut.
• Charging. "$|T|\le |F|$" is proved by an injection from $T$ into $F$, not by counting. The injection is the step a grader looks for.
• Case split. The construction needs a non-adjacent pair, so the complete bipartite case is handled separately, by counting.

When the inequalities are strict

Both inequalities can be strict, separately or together. Computed with the brute-force helpers above:

shared = network(K4_left + [(a + 3, b + 3) for a, b in K4_left])   # both contain vertex 3
bridge = network(K4_left + K4_right + [(3, 4)])
petersen = network([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
                   + [(5, 7), (7, 9), (9, 6), (6, 8), (8, 5)])
def delta(g):
    return min(len(g[v]) for v in g)
rows = [(kappa(g), kappa_edges(g), delta(g)) for g in (shared, bridge, N, petersen)]
assert rows == [(1, 3, 3), (1, 1, 3), (1, 2, 3), (3, 3, 3)]

For 3-regular graphs the first inequality is always an equality: if $G$ is 3-regular, then $\kappa (G)={\kappa }^{\prime }(G)$ (West, Theorem 4.1.11). We state it without proof here. The Petersen graph is an instance: $\kappa ={\kappa }^{\prime }=3$.

What a certificate costs

A separating set of size $k$ proves $\kappa (G)\le k$, and anyone can check it with one search over the remaining graph, in $O(n+m)$ time. An edge cut proves ${\kappa }^{\prime }(G)\le k$ the same way. The lemma above means a search for ${\kappa }^{\prime }$ needs only the $2^{n-1}-1$ splits of the vertices, not the $2^m$ sets of edges. For $N$ that is 127 splits against 16,384 edge sets:

assert 2 ** (8 - 1) - 1 == 127 and 2 ** 14 == 16_384

Proving the lower bound, that no smaller cut exists, is a different matter. Short evidence for it exists too: for every two non-adjacent vertices, $k$ paths between them that share no internal vertex ($\kappa (G)\ge k$ holds exactly when such paths exist for every non-adjacent pair, in a graph that is not complete). That is Menger's theorem, two modules from now.

A problem that looks different

A town wants to make every street one-way, and still let every resident drive from any corner to any other. For which street maps is that possible? If one street is the only link between two halves of town, it clearly fails. Is that the only obstacle? Nothing in the question mentions cuts. The lab's last exercise is a different problem that also hides its structure.

Practise

The lab runs in your browser. Your own code turns an edge cut into a separating set, one charged edge per frame, the way the proof does. Then you compute ${\kappa }^{\prime }$ by searching splits of the vertices, and watch a tempting shortcut fail. Half of the lab is proofs. You assemble a proof about the ends of a cut edge, with decoys among the steps. You find the false step in a convincing argument and build a counterexample in code. And you finish with a growing network that does not say what it is, where you write the proof yourself and check it against explicit criteria.

Recap

• You can now: define $\kappa$ and ${\kappa }^{\prime }$ with their conventions; prove that every disconnecting set contains an edge cut; characterize cut edges as the edges on no cycle; prove Whitney's inequality by charging a vertex cut to a minimum edge cut; and give graphs where each inequality is strict.
• Invariant: in Whitney's construction, every $x,y$-path leaves $X$ through an edge whose $X$ end is $x$ (then its $Y$ end is in $T$) or another vertex with a neighbor in $Y$ (in $T$), and each vertex of $T$ is charged to its own edge of $F$.
• Complexity achieved: a cut is checked in $O(n+m)$ time, and ${\kappa }^{\prime }$ needs a search over $2^{n-1}-1$ vertex splits instead of $2^m$ edge sets.
• Failure mode: reading $\kappa (G)=k$ for "$G$ is $k$-connected", and forgetting the convention $\kappa (K_n)=n-1$.
• In real software: NetworkX's node_connectivity and edge_connectivity compute $\kappa$ and ${\kappa }^{\prime }$ by maximum-flow computations, not by subset search.
• Retrieval: module 11 certified a maximum matching with a vertex cover of the same size. What plays the role of the cover for "no separating set has fewer than $k$ vertices"? ($k$ internally disjoint paths for every non-adjacent pair: Menger's theorem, module 16.)

Check yourself

After the lab, the tutor will ask you to defend your work out loud:

1. Where does the proof of $\kappa \le {\kappa }^{\prime }$ use that $x$ and $y$ are not adjacent, and how is the complete bipartite case handled instead?
2. Why does a disconnecting set of a connected graph contain an edge cut, and why does that let a search for ${\kappa }^{\prime }$ range over splits of the vertices?
3. Two $K_4$'s sharing one vertex have $\kappa =1<{\kappa }^{\prime }=3$. Which vertex is the cut vertex, and why does no set of two edges disconnect the graph?

Topic list modeled on the public syllabus of UIUC Math 412 (Graph Theory), which follows D. B. West, Introduction to Graph Theory, 2nd ed., Chapters 1–7. All lessons, proofs, examples, code and exercises here are original. This course is independent and not affiliated with or endorsed by the University of Illinois.