The Claim and Its Hypotheses
An open ear adds a path whose endpoints are already in a graph and whose internal vertices are new. The key feature is that the ear has two distinct endpoints: after one vertex is deleted, the parts of the ear that remain can still attach to the original graph. This tutorial proves that the enlarged graph remains 2-connected, including when the ear is just one new edge.
All graphs in this tutorial are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. A graph is connected if each pair of its vertices is joined by a path; a graph with one vertex is connected. A vertex \(v\) is a cut vertex if deleting \(v\) and all incident edges makes a connected graph disconnected.
The equivalence follows directly from the definitions: for a connected graph, a vertex is a cut vertex exactly when its deletion leaves a disconnected graph. The order condition matters: it rules out calling a graph with fewer than three vertices 2-connected just because deleting a vertex leaves a connected graph.
The endpoints being distinct is essential to the argument. When an ear has internal vertices, deleting an internal vertex divides the path into at most two pieces, and those pieces attach to different endpoints in \(H\). When the ear has no internal vertices, it simply adds an edge between existing vertices.
Why the Addition Preserves 2-Connectivity
Proof. Let the endpoints of \(P\) be \(a\) and \(b\). Since \(H\) is connected and both endpoints lie in \(H\), every vertex of \(P\) can reach \(H\) along \(P\); thus \(G\) is connected. Also, \(V(H)\subseteq V(G)\), so \(G\) has at least three vertices. It remains to prove that \(G-v\) is connected for every \(v\in V(G)\).
First suppose \(P\) has no internal vertices, so it consists of the new edge \(ab\). For any \(v\in V(H)\), the graph \(H-v\) is connected because \(H\) is 2-connected. If \(v=a\) or \(v=b\), the new edge is deleted with \(v\); otherwise it remains an edge between vertices already in \(H-v\). In either case, \(G-v\) is connected.
Now suppose \(P\) has at least one internal vertex. If \(v\in V(H)\), then \(H-v\) is connected. If \(v\) is neither endpoint of \(P\), the whole ear remains and attaches to \(H-v\) at \(a\) and \(b\). If \(v=a\), the remaining part of the ear attaches to \(H-v\) at \(b\); if \(v=b\), it attaches at \(a\). Thus \(G-v\) is connected in each case.
Finally, suppose \(v\) is an internal vertex of \(P\). The graph \(H\) remains intact and is connected. Deleting \(v\) divides \(P\) into a part attached to \(a\) and a part attached to \(b\); either part may contain no edge if \(v\) is next to an endpoint. Every remaining vertex of \(P\) lies in one of these parts, and each nonempty part is connected to \(H\) through its endpoint. Hence every vertex of \(G-v\) lies in the same connected graph as \(H\). We have proved that \(G-v\) is connected for every \(v\), so \(G\) is 2-connected. \(\square\)
These cases cover every vertex of \(G\): vertices already in \(H\), including either ear endpoint, and internal vertices that are new. The proof does not claim that \(G-v\) stays connected because the ear itself stays intact. It may not; the important point is that each remaining piece still has a route into \(H\).
Worked Examples
Worked Example: An Ear with Two Internal Vertices
Let \(H\) have vertex set \(\{a,b,c\}\) and edge set \(\{ab,bc,ca\}\). This triangle is connected, and deleting any one vertex leaves the edge between the other two, so \(H\) is 2-connected. Add the open ear \(P=a-x-y-b\), whose internal vertices are \(x,y\). The resulting graph has vertex set \(\{a,b,c,x,y\}\) and edge set \(\{ab,bc,ca,ax,xy,yb\}\).
To verify 2-connectivity directly, delete each vertex in turn. In the table, the listed path or paths together cover all remaining vertices and join them into a connected graph.
| Deleted vertex | Paths showing the remaining graph is connected |
|---|---|
| \(a\) | \(c-b-y-x\) |
| \(b\) | \(c-a-x-y\) |
| \(c\) | \(a-x-y-b\), with edge \(ab\) also present |
| \(x\) | \(c-b-y\) and \(b-a\) |
| \(y\) | \(b-a-x\) and \(a-c\) |
For example, when \(x\) is deleted, the remaining vertices are \(\{a,b,c,y\}\). The path \(c-b-y\) joins \(c,b,y\), and the edge \(ba\) attaches \(a\) to that path. Each other row checks the corresponding deletion, so the graph is connected and remains connected after every single-vertex deletion.
Check: there are five vertices, and the table covers all five possible deletions. In particular, deleting an internal vertex does not strand the rest of the ear: after deleting \(x\), the segment \(y-b\) still attaches at \(b\); after deleting \(y\), the segment \(a-x\) still attaches at \(a\).
Worked Example: An Ear with No Internal Vertices
Let \(H\) have vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34,41\}\), the cycle \(C_4\). It is 2-connected: deleting any one vertex leaves a path on the other three vertices. Add the length-one open ear \(P=1-3\). The resulting graph has the same vertex set and edge set \(\{12,23,34,41,13\}\).
Here the new ear adds an edge, not a vertex. The deletion checks are: deleting \(1\) leaves the path \(2-3-4\); deleting \(2\) leaves the path \(3-4-1\) together with edge \(13\); deleting \(3\) leaves the path \(2-1-4\); and deleting \(4\) leaves the triangle with edges \(12,23,13\). Each remaining graph is connected.
Check: the original cycle already has four vertices, and adding \(13\) does not change that vertex set. The edge \(13\) is absent from \(E(H)\), so this is a genuine ear addition. The four deletion checks show directly that the enlarged graph is 2-connected.
Worked Example: Adding Two Ears in Succession
Start with the triangle \(H\) on vertex set \(\{a,b,c\}\) and edge set \(\{ab,bc,ca\}\). First add the ear \(a-x-b\). Then, in the graph now obtained, add the ear \(c-y-x\), whose endpoints \(c,x\) are distinct vertices of that graph and whose internal vertex \(y\) is new. The final graph has vertex set \(\{a,b,c,x,y\}\) and edge set \(\{ab,bc,ca,ax,xb,cy,yx\}\).
The theorem applies to the first addition because the triangle is 2-connected. It applies again to the second addition because the first enlarged graph is 2-connected. To check the final result directly, the following paths cover the remaining vertices after each deletion:
| Deleted vertex | Paths showing the remaining graph is connected |
|---|---|
| \(a\) | \(b-c-y-x\) |
| \(b\) | \(c-a-x-y\) |
| \(c\) | \(a-x-y\) and \(x-b\) |
| \(x\) | \(a-c-y\) and \(a-b\) |
| \(y\) | \(c-b-a-x\) |
For instance, when \(c\) is deleted, \(a-x-y\) joins \(a,x,y\), and edge \(xb\) attaches \(b\). Thus that deletion also leaves a connected graph. Together, the checks account for every vertex, in agreement with applying the theorem twice.
Check: the second ear is valid relative to the first enlarged graph: \(c\) and \(x\) are already present, they are distinct, and \(y\) is not yet present. Its edges \(cy,yx\) are new. The final graph has five vertices, and every one of its five possible single-vertex deletions is covered above.
Repeated Additions and a Common Pitfall
Proof. Let \(H_0\) be the starting 2-connected graph, and let \(H_i\) be the graph after the \(i\)th addition. We use induction on the number of additions. For zero additions, \(H_0\) is 2-connected by assumption. Suppose \(H_i\) is 2-connected. The next ear is open relative to \(H_i\), so the theorem gives that \(H_{i+1}\) is 2-connected. This proves the claim for every finite number of additions. \(\square\)
Common pitfall: treating a one-ended attachment as an open ear. The theorem does not say that adding any path to a 2-connected graph preserves 2-connectivity. For a concrete counterexample, start with the triangle on vertex set \(\{a,b,c\}\) and edge set \(\{ab,bc,ca\}\), then add the path \(a-x-y\). The resulting graph has vertex set \(\{a,b,c,x,y\}\) and edge set \(\{ab,bc,ca,ax,xy\}\). This path has only one endpoint in the triangle, so it is not an open ear. Deleting \(a\) leaves the edge \(bc\) and the edge \(xy\), with no edge between \(\{b,c\}\) and \(\{x,y\}\). The remaining graph is disconnected, so the conclusion fails. The missing second endpoint is exactly what the proof needs to keep the remaining path attached when a vertex is deleted.
The result matters because it gives a reliable way to build larger 2-connected graphs while preserving their connectivity property at every step. For a single edge ear, no new vertex needs checking; for a longer ear, the internal-vertex case is handled by the two attachments to the original graph. In either case, the decisive test is whether deleting any one vertex leaves the entire graph connected.
Check Your Understanding
For each question, use the definition of an open ear and the single-vertex deletion test.
- Why must the endpoints of an open ear be distinct for the proof of the theorem?
- A 2-connected graph gains a new edge between two existing vertices. Which case of the proof verifies that the result is 2-connected?
- When an internal vertex of an ear is deleted, where do the remaining parts of the ear attach?
- Let \(H\) be a 2-connected graph and add a path with two endpoints in \(H\) but one internal vertex outside \(H\). State the hypotheses that make this an open ear.
- In the one-ended example above, identify a vertex whose deletion disconnects the enlarged graph and name the resulting components.