2-Connected Graphs and Ear Decompositions

The question

Six routers and nine cables: two triangles, $0,1,2$ and $3,4,5$, joined by the three cables $0$–$3$, $1$–$4$ and $2$–$5$. This graph is called the prism.

Whichever single router fails, the other five can still reach each other. You can check that by deleting each router in turn. But that is six separate experiments, and it does not tell you why the network is robust, or how to design another one that is. This module gives two better answers. The first is local: between any two routers there are two routes that share no router in between. The second is a recipe: the network can be built from a cycle by repeatedly adding a path between two routers already present. Both turn out to be equivalent to "no single failure disconnects".

The naive approach, and where it wastes work

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=()):
    gone = set(removed)
    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:
                seen.add(w)
                queue.append(w)
    return len(seen) == len(left)

def two_connected(g):
    """By brute force: at least 3 vertices, connected, and no single deletion disconnects."""
    return len(g) >= 3 and connected(g) and all(connected(g, [v]) for v in g)

prism = network([(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (0, 3), (1, 4), (2, 5)])
assert two_connected(prism)

The brute-force test deletes each of the $n$ vertices and searches what is left: $n$ searches, each over the whole graph. It answers "yes" or "no" but leaves no evidence behind, and it says nothing about how to build such a network. Each deletion re-explores almost the same graph.

Definitions

A graph $G$ is 2-connected if it has at least 3 vertices, is connected, and has no cut vertex. (This is $\kappa (G)\ge 2$ from module 14. The complete graph $K_2$ has no cut vertex but only two vertices, and $\kappa (K_2)=1$, so it is not 2-connected.)

Two $u,v$-paths are internally disjoint if they share no vertex other than $u$ and $v$. In the prism, $0,3,4$ and $0,1,4$ are internally disjoint $0,4$-paths.

Whitney's theorem

Proof. If. Suppose every pair has two internally disjoint paths. Deleting one vertex $x$ cannot separate two other vertices $u$ and $v$, because $x$ lies on at most one of their two paths. So $G-x$ is connected for every $x$, and $G$ is connected, with at least 3 vertices.

Only if. Let $G$ be 2-connected. We prove by induction on the distance $d(u,v)$ that every two vertices $u\ne v$ have two internally disjoint $u,v$-paths.

Base, $d(u,v)=1$. The edge $uv$ is one path. $G-uv$ is still connected: otherwise $uv$ is a cut edge, and since $G$ has at least 3 vertices, one of $u,v$ has another neighbor and is a cut vertex. So $G-uv$ has a $u,v$-path, which is the second.

Step, $d(u,v)=k\ge 2$. Let $w$ be the vertex before $v$ on a shortest $u,v$-path, so $d(u,w)=k-1$. By induction there are internally disjoint $u,w$-paths $P$ and $Q$. Since $G$ is 2-connected, $G-w$ has a $u,v$-path $R$.

• If $v$ lies on $P$ or $Q$, say on $P$, then $P$ up to $v$, and $Q$ followed by the edge $wv$, are internally disjoint $u,v$-paths.
• Otherwise let $z$ be the last vertex of $R$ that lies on $P\cup Q$. ($R$ starts at $u$, so such a vertex exists.) Say $z$ is on $P$. Then $P$ from $u$ to $z$ followed by $R$ from $z$ to $v$ is one path, and $Q$ followed by $wv$ is the other. They are internally disjoint: the part of $R$ after $z$ meets neither $P$ nor $Q$, because $z$ was the last such vertex; and $P$ and $Q$ are internally disjoint by induction. $◻$

Proof moves used here.

• Induction on the distance between $u$ and $v$, so the step can use the two paths to the vertex one before $v$.
• Extremal choice. $z$ is the last vertex of $R$ on $P\cup Q$. That is what guarantees the tail of $R$ avoids both paths.
• Case split. The case where $v$ is already on $P$ or $Q$ is handled first, so the main case can assume it is not.

The expansion lemma

Expansion lemma. If $G$ is 2-connected and $G^{\prime }$ is obtained by adding a new vertex $y$ adjacent to at least two vertices of $G$, then $G^{\prime }$ is 2-connected.

Proof. $G^{\prime }$ has at least 4 vertices and is connected. Delete one vertex. Deleting $y$ leaves $G$, which is connected. Deleting some $x$ of $G$ leaves $G-x$, connected because $G$ is 2-connected, together with $y$, which still has a neighbor in $G-x$ because it had at least two. So no vertex of $G^{\prime }$ is a cut vertex. $◻$

Cycles through any two vertices

Two internally disjoint $u,v$-paths together form a cycle through $u$ and $v$, and a cycle through $u$ and $v$ splits at them into two such paths. So Whitney's theorem can be restated:

Corollary. A graph with at least 3 vertices is 2-connected if and only if every two of its vertices lie on a common cycle.

In the prism, $0$ and $4$ lie on the cycle $0,3,4,1$:

def internally_disjoint(p, q):
    return p[0] == q[0] and p[-1] == q[-1] and not set(p[1:-1]) & set(q[1:-1])

def is_path(g, p):
    return len(set(p)) == len(p) and all(b in g[a] for a, b in zip(p, p[1:]))

p, q = [0, 3, 4], [0, 1, 4]
assert is_path(prism, p) and is_path(prism, q) and internally_disjoint(p, q)

Ear decompositions, traced on the prism

An ear of a subgraph $H$ is a path in $G$ whose two endpoints are distinct vertices of $H$, whose other vertices (if any) are not in $H$, and whose edges are not in $H$. A single edge of $G$ outside $H$ between two vertices of $H$ counts. An ear decomposition of $G$ is a sequence: a cycle, then ears added one at a time, until every edge of $G$ is used.

Here is one for the prism. Start with the triangle $0,1,2$; add the ear $0,3,4,1$; then the ear $2,5,4$; then the single-edge ear $3$–$5$:

def valid_ears(g, cycle, ears):
    """Check an ear decomposition (a stand-in checker, not a way to find one)."""
    if len(cycle) < 3 or not is_path(g, cycle) or cycle[0] not in g[cycle[-1]]:
        return False
    built = set(cycle)
    used = {frozenset(e) for e in zip(cycle, cycle[1:] + cycle[:1])}
    for ear in ears:
        ends, inside = (ear[0], ear[-1]), ear[1:-1]
        new = {frozenset(e) for e in zip(ear, ear[1:])}
        if ends[0] == ends[1] or not set(ends) <= built or set(inside) & built or not is_path(g, ear):
            return False
        if new & used:
            return False
        used |= new
        built |= set(inside)
    return built == set(g) and used == {frozenset((u, w)) for u in g for w in g[u]}

assert valid_ears(prism, [0, 1, 2], [[0, 3, 4, 1], [2, 5, 4], [3, 5]])
assert not valid_ears(prism, [0, 1, 2], [[0, 1], [0, 3, 4, 1], [2, 5, 4], [3, 5]])   # 0-1 is reused

Proof. If. A cycle is 2-connected. Adding an ear to a 2-connected $H$ keeps it 2-connected: the new graph has at least 3 vertices and is connected. Delete a vertex $x$. If $x$ is in $H$, then $H-x$ is connected, and the ear, minus $x$ if $x$ is an endpoint, still hangs from the other endpoint, which is in $H-x$ because the endpoints are distinct. If $x$ is inside the ear, $H$ is untouched and each remaining piece of the ear is attached to an endpoint. Either way the rest is connected.

Only if. Let $G$ be 2-connected and $C$ any cycle of it (one exists: by the corollary, any two vertices lie on a cycle). Among the subgraphs that can be built from $C$ by adding ears, take a maximal one, $H$. Suppose $H\ne G$.

• If some edge of $G$ outside $H$ joins two vertices of $H$, that edge is an ear, contradicting maximality.
• Otherwise some vertex is missing from $H$. Since $G$ is connected, there is an edge $uw$ with $u\in H$ and $w\notin H$. Since $G$ is 2-connected, $G-u$ is connected, so it has a path from $w$ to a vertex of $H-u$ (which is nonempty, as $H$ contains a cycle). Let $z$ be the first vertex of $H$ on that path. Then $u$, $w$, then the path up to $z$, is an ear of $H$: its ends $u\ne z$ are in $H$, and its inner vertices are not. Again maximality is contradicted.

So $H=G$, and $G$ has an ear decomposition starting from $C$. $◻$

Proof moves used here.

• Extremal choice: a maximal subgraph built by ears, so that "it cannot grow" becomes a hypothesis to contradict.
• Case split on whether a missing edge or a missing vertex is what stops $H$ from being $G$.
• Where the hypothesis is used: $G-u$ connected is exactly what lets the ear return to $H$ at a vertex other than $u$.

When an ear closes on itself

The word distinct in "two distinct endpoints" matters. Take two copies of $K_4$ that share one vertex. You can start from a triangle in one copy and add ears until that copy is used up. To reach the other copy, any path from the first must leave and return through the shared vertex, so it is a closed ear: both ends are the same vertex. That graph has a cut vertex, so it is not 2-connected, and indeed it has no ear decomposition with open ears.

left = list(combinations(range(4), 2))
shared = network(left + [(a + 3, b + 3) for a, b in left])   # both copies contain vertex 3
assert not two_connected(shared) and not connected(shared, [3])

What a certificate costs

An ear decomposition is a certificate of 2-connectedness: checking one, as valid_ears does, takes one pass over the edges. A cut vertex is a certificate of the opposite: delete it and search once. The brute-force test instead runs $n$ searches. Hopcroft and Tarjan (1973) found all cut vertices of a graph in one depth-first search, in $O(n+m)$ time.

A problem that looks different

A depot ships to three warehouses through a network of hubs. A hub can fail, and the company wants routes from the depot to the three warehouses that share no hub at all, so that one failure costs at most one delivery. When can it be done, and what short evidence shows it cannot? Nothing in the question mentions cycles or ears. It is a question about routes that avoid each other, and module 16 answers it.

Practise

The lab runs in your browser. Your code grows an ear decomposition one ear per frame and refuses to be fooled by an ear that closes on itself. It then finds two disjoint routes where the obvious first choice blocks the second. Half of the lab is proofs. You assemble a proof that a small change to a 2-connected graph keeps it 2-connected, find the broken step in a near-copy of Whitney's proof and build the graph that breaks it, and finish with a problem that names no technique, where you write the proof yourself.

Recap

• You can now: prove Whitney's theorem by induction on distance; prove the expansion lemma; restate 2-connectivity with cycles; define ears and ear decompositions; and prove that a graph is 2-connected exactly when it has one, from any starting cycle.
• Invariant: in Whitney's proof, the tail of $R$ after its last vertex on $P\cup Q$ meets neither path; in the ear theorem, every stage of the construction is 2-connected.
• Complexity achieved: an ear decomposition is checked in $O(n+m)$; finding cut vertices takes one depth-first search, $O(n+m)$, against $n$ searches by brute force.
• Failure mode: allowing an ear whose two ends coincide, and forgetting the hypothesis of at least 3 vertices ($K_2$).
• In real software: NetworkX's is_biconnected and articulation_points find cut vertices with a depth-first search (the Hopcroft–Tarjan approach).
• Retrieval: module 14 asked how many vertices must fail before a graph splits. In those terms, what is a 2-connected graph? (One with $\kappa \ge 2$: no single vertex failure splits it.)

Check yourself

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

1. In the step of Whitney's proof, why is the case "$v$ lies on $P$ or $Q$" handled separately?
2. In the proof of the ear theorem, where is 2-connectedness used, and what goes wrong in a graph with a cut vertex?
3. Two copies of $K_4$ sharing one vertex: which ears can you add after the first copy, and why is none of them open?

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.