Whitney's Ear-Decomposition Characterization

From Cycles to 2-Connected Graphs

A cycle has no cut vertex: deleting any one of its vertices leaves a connected path. An open ear adds a path between two distinct vertices already present, with all its internal vertices new. The endpoints give the new path two attachments to the existing graph. Whitney’s characterization says that this construction is not just a way to make some 2-connected graphs: it builds every finite 2-connected graph with at least three vertices.

Throughout, graphs are finite and simple. A graph is connected if every pair of its vertices is joined by a path. A cut vertex is a vertex whose deletion increases the number of connected components. A graph is 2-connected if it is connected, has at least three vertices, and has no cut vertex. In particular, deleting any one vertex from a 2-connected graph leaves a connected graph.

Definition: Let \(H\) be a subgraph of a graph \(G\). An open ear of \(H\) is a path \(P=v_0v_1\cdots v_\ell\), where \(\ell\geq 1\), whose distinct endpoints \(v_0,v_\ell\) belong to \(H\), and whose internal vertices \(v_1,\dots,v_{\ell-1}\) do not belong to \(H\). Its edges are not already in \(H\). When \(\ell=1\), the ear is a single missing edge between two vertices of \(H\).

Definition: An open ear decomposition of \(G\) is a sequence of subgraphs \(G_0,G_1,\dots,G_k\) such that \(G_0\) is a cycle, and for each \(i\geq1\), \(G_i\) is obtained from \(G_{i-1}\) by adding an open ear of \(G_{i-1}\). The final subgraph \(G_k\) is \(G\), so the decomposition includes every vertex and every edge of \(G\).

The requirement that the final subgraph equal \(G\) matters: a cycle may be a subgraph of a graph without providing a decomposition of the entire graph. The ear definition allows a single-edge addition, which is necessary when all vertices have already appeared but some edges are still missing.

Why Adding an Ear Preserves 2-Connectivity

Lemma: If \(H\) is 2-connected and \(P\) is an open ear of \(H\), then the graph \(H\cup P\) is 2-connected.

Proof. Write the ear as \(P=v_0v_1\cdots v_\ell\), with distinct endpoints \(v_0,v_\ell\) in \(H\). The union is connected because \(H\) is connected and every vertex of \(P\) is joined along \(P\) to an endpoint in \(H\). It has at least three vertices because \(H\) already has at least three.

Now delete a vertex \(x\) of \(H\cup P\). If \(x\) is an internal vertex of \(P\), the remaining parts of \(P\) attach to \(H\) at \(v_0\) and \(v_\ell\), and \(H\) remains connected. Thus all remaining vertices lie in one connected component. If \(x\) belongs to \(H\), then \(H-x\) is connected by 2-connectivity. When \(x\) is not an endpoint of \(P\), the whole ear still attaches to \(H-x\) at both endpoints. When \(x\) is an endpoint, the remaining portion of the ear, if any, attaches to \(H-x\) at the other endpoint. If the ear has length one, deleting an endpoint simply removes that ear edge. In every case, the graph after deletion is connected. Hence \(H\cup P\) has no cut vertex and is 2-connected. \(\square\)

This lemma proves one direction of the characterization once we start with a cycle. It also explains the endpoint condition: each newly added portion must remain connected to the old graph after deletion of any one vertex.

Worked Example: Building \(K_4\) by Open Ears

Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,13,14,23,24,34\}\). Start with the cycle \(G_0\) on vertices \(\{1,2,3\}\), with edges \(\{12,23,31\}\).

Add the path \(1-4-2\). Its endpoints \(1,2\) are distinct vertices of \(G_0\), and its internal vertex \(4\) is new. Its edges \(14,42\) are new, so this is an open ear. The resulting graph \(G_1\) has vertices \(\{1,2,3,4\}\) and edges \(\{12,23,31,14,24\}\).

The only edge of \(G\) not yet included is \(34\). Add the one-edge path \(3-4\), whose endpoints are distinct vertices of \(G_1\). This gives \(G_2=G\). The edge count checks the construction: the starting cycle has \(3\) edges, the first ear adds \(2\), and the last ear adds \(1\), for \(3+2+1=6=|E|\).

Check: the lemma guarantees 2-connectivity. Directly, deleting \(1,2,3,4\), respectively, leaves edge sets \(\{23,24,34\}\), \(\{13,14,34\}\), \(\{12,14,24\}\), and \(\{12,23,13\}\). Each remaining graph is connected, confirming the result.

Extending a Cycle in a 2-Connected Graph

For the converse, we need to know that an existing 2-connected subgraph can be enlarged by an ear unless it already equals the whole graph. The key is to look at components outside that subgraph. A component outside cannot attach to the subgraph at only one vertex: that vertex would separate the component from the rest of the subgraph.

Lemma: Let \(G\) be 2-connected, and let \(H\) be a 2-connected subgraph of \(G\). If \(H\neq G\), then there is an open ear of \(H\) whose vertices and edges belong to \(G\).

Proof. First suppose that \(H\) does not contain every vertex of \(G\). Consider a connected component \(C\) of the subgraph induced by the vertices outside \(H\). Define its attachment set \(A\) to be the vertices of \(H\) adjacent in \(G\) to at least one vertex of \(C\). If \(A\) had only one vertex \(x\), then deleting \(x\) would leave \(C\) with no edge to \(H-x\). It would also have no edge to any other component outside \(H\), since distinct components have no edges between them. Because \(H-x\) is nonempty, \(G-x\) would be disconnected, contradicting that \(G\) has no cut vertex. Therefore \(A\) contains two distinct vertices \(a,b\).

Choose vertices \(c,d\) of \(C\) adjacent to \(a,b\), respectively. Since \(C\) is connected, it contains a path from \(c\) to \(d\); choose one with no repeated vertices. Joining the edge \(ac\), this path, and the edge \(db\) gives a path from \(a\) to \(b\) whose internal vertices lie outside \(H\). If \(c=d\), the path inside \(C\) has length zero and the joined path is \(a-c-b\). In either case this is an open ear of \(H\) in \(G\).

Now suppose \(H\) contains every vertex of \(G\). Since \(H\neq G\), some edge \(ab\) of \(G\) is missing from \(H\). Its endpoints are distinct because \(G\) is simple. The single-edge path \(a-b\) is then an open ear of \(H\). This proves the lemma in both cases. \(\square\)

To begin the construction, a 2-connected graph must contain a cycle. Here is a brief justification. Every vertex has degree at least two: a vertex of degree one would become isolated after its sole neighbor was deleted, while at least one other vertex would remain because the graph has at least three vertices. Take a longest path with no repeated vertices. Every neighbor of one endpoint lies on that path, or the path could be extended. The endpoint has at least two neighbors, so one is not just its predecessor. The segment of the path between that neighbor and the endpoint, together with their joining edge, forms a cycle.

Theorem (Whitney’s Ear-Decomposition Characterization): A finite simple graph \(G\) with at least three vertices is 2-connected if and only if it has an open ear decomposition beginning with a cycle.

Proof. Suppose first that \(G\) has such a decomposition. Its initial graph \(G_0\), a cycle, is 2-connected: deleting any vertex leaves a connected path. Apply the ear-addition lemma to each successive ear. Inductively, every \(G_i\) is 2-connected, so the final graph \(G\) is 2-connected.

Conversely, suppose \(G\) is 2-connected. By the cycle argument above, choose a cycle \(G_0\) in \(G\). If the current subgraph \(G_i\) is not all of \(G\), it is 2-connected: this holds initially and remains true whenever an ear is added, by the ear-addition lemma. The extension lemma therefore supplies an open ear of \(G_i\) in \(G\). Add it to obtain \(G_{i+1}\).

Each step adds at least one edge of \(G\) that was not in the current subgraph. Since \(G\) has finitely many edges, this process must stop after finitely many steps. It cannot stop while a vertex or edge of \(G\) is missing, because the extension lemma would then supply another ear. Thus the final subgraph is \(G\), giving an open ear decomposition. \(\square\)

Using the Characterization

Worked Example: A Six-Vertex Decomposition

Let \(G\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,14,25,56,46,13\}\). Begin with the cycle \(1-2-3-4-1\), whose edges are \(12,23,34,14\).

Add the ear \(2-5-6-4\). Its endpoints \(2,4\) are distinct vertices of the cycle; its internal vertices \(5,6\) are new. The ear contributes exactly the edges \(25,56,64\). Add the one-edge ear \(1-3\), whose endpoints are already present and distinct. All listed edges have now been included: the cycle contributes \(4\), the first ear contributes \(3\), and the last contributes \(1\), totaling \(4+3+1=8=|E|\).

Check: the theorem gives 2-connectivity. Deleting vertices \(1,2,3,4,5,6\) in turn leaves connected graphs: after deleting \(1\), the remaining vertices connect through \(2-3-4\) and \(2-5-6-4\); after deleting \(2\), through \(3-4-1\) and \(4-6-5\); after deleting \(3\), through \(1-2-5-6-4\); after deleting \(4\), through \(1-2-3\) and \(2-5-6\); after deleting \(5\), the cycle remains with vertex \(6\) attached at \(4\); after deleting \(6\), the cycle remains with vertex \(5\) attached at \(2\).

Worked Example: Why a Pendant Vertex Prevents a Decomposition

Let \(G\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,ca,cd\}\). The triangle \(a-b-c-a\) is a cycle, but it does not include \(d\). Moreover, deleting \(c\) leaves the edge \(ab\) and the isolated vertex \(d\), so \(G-c\) is disconnected. Thus \(c\) is a cut vertex and \(G\) is not 2-connected.

The theorem rules out an open ear decomposition of the whole graph. Indeed, an ear cannot introduce \(d\) as a new endpoint: both endpoints must already be present. Nor can it introduce \(d\) as an internal vertex of a path and leave it with degree one, since an internal vertex has two incident path edges. The triangle therefore cannot be extended by valid open ears to this graph.

Check: the graph has \(4\) vertices and \(4\) edges, but the obstruction is not the edge count. It is the cut vertex \(c\), which contradicts the necessary 2-connectivity in Whitney’s characterization.

A Common Mistake

A frequent error is to call any path that adds a new vertex an open ear. For the triangle with edges \(12,23,31\), one might try to add the edge \(14\) as an ear. This is invalid: vertex \(4\) is not in the existing subgraph, so the edge \(1-4\) does not have both endpoints in that subgraph. The resulting graph has a pendant vertex and is not 2-connected. A valid ear must have two distinct old endpoints; new vertices, if present, occur strictly inside the path. This endpoint condition is exactly what lets the ear attach to the old graph at both ends.

Check Your Understanding

Use the definitions and the two directions of the characterization to answer the following.

Give an open ear decomposition of the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,14,24,34\}\).
Why must the attachment set of a component outside a 2-connected subgraph contain at least two vertices?
Explain why an ear of length one is allowed, and state the condition its endpoints must satisfy.
Prove that a cycle is 2-connected using the definition involving deletion of a vertex.
Can a graph with a cut vertex have an open ear decomposition beginning with a cycle? Justify your answer using the theorem.