Finding an Ear in a 2-Connected Graph

Why an Ear Must Be Available

An ear is a path that joins two vertices of a subgraph while using new vertices in between. The key question is when such a path is guaranteed to exist. Here, the guarantee comes from 2-connectivity: a component lying outside a 2-connected subgraph cannot connect to the rest of the graph through just one vertex. Two distinct attachment vertices allow us to build a path that enters and leaves that component, producing an ear.

All graphs in this tutorial 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. We call a graph 2-connected if it has at least three vertices, is connected, and has no cut vertex. A subgraph \(H\) of \(G\) may omit vertices, edges, or both; it is proper if \(H\ne G\).

For a component \(C\) of the subgraph induced by the vertices outside \(H\), its attachment set in \(H\) is the set of vertices of \(H\) adjacent to at least one vertex of \(C\). It counts distinct vertices, not edges. If the attachment set contains distinct vertices \(x\) and \(y\), a path through \(C\) from a neighbor of \(x\) to a neighbor of \(y\), together with the edges to \(x\) and \(y\), is a candidate ear.

The Attachment Lemma

Proof. Let \(C\) be a component of \(G-V(H)\), and let \(S\) be its attachment set in \(H\). Suppose that \(S\) has at most one vertex. If \(S=\{x\}\), consider \(G-x\). The vertices of \(C\) have no neighbors in \(H-x\), by the definition of \(S\). They also have no edges to another component of \(G-V(H)\), because distinct components have no edges between them. Thus \(C\) has no path to \(H-x\) in \(G-x\). The graph \(H-x\) has at least two vertices and is connected, since \(H\) is 2-connected. Therefore \(G-x\) is disconnected, making \(x\) a cut vertex of \(G\), a contradiction. If \(S=\varnothing\), then \(C\) has no neighbors in \(H\); since \(G\) is connected, this is impossible. Hence \(|S|\ge2\). \(\square\)

The argument uses the full strength of the hypothesis on \(H\): after deleting one possible attachment vertex \(x\), the remaining vertices of \(H\) are still connected and nonempty. The hypothesis on \(G\) rules out the resulting separation. Once two attachments are known, only connectedness of the outside component is needed to find a path between them.

Finding the Ear

Proof. First suppose \(V(H)\ne V(G)\). Choose a component \(C\) of \(G-V(H)\). By the attachment lemma, \(C\) has distinct attachment vertices \(x,y\in V(H)\). Choose a vertex \(a\in C\) adjacent to \(x\), and a vertex \(b\in C\) adjacent to \(y\). Because \(C\) is connected, there is an \(a\)-\(b\) path in \(C\). Choose one with the fewest edges; it has no repeated vertices, since removing the portion between two repeated occurrences would give a shorter walk and hence a shorter path. If \(a=b\), use the length-zero path consisting of that single vertex. Prepending the edge \(xa\) and appending the edge \(by\) gives a path from \(x\) to \(y\). Its internal vertices all lie in \(C\), so they are outside \(H\); its endpoints are distinct vertices of \(H\). It is therefore an open ear of \(H\).

Now suppose \(V(H)=V(G)\). Because \(H\) is proper, some edge \(uv\) belongs to \(E(G)\setminus E(H)\). The edge \(uv\) is a path with distinct endpoints in \(H\) and no internal vertices. It is an open ear by the definition. These cases cover every proper subgraph \(H\), proving the theorem. \(\square\)

This is an existence proof that also gives a construction: find an outside component, identify two of its attachments, and connect neighbors of those attachments by a path inside the component. The earlier result on adding an ear shows that adjoining the ear to \(H\) gives a larger 2-connected subgraph. The theorem here supplies the ear; it does not require the ear to use every vertex outside \(H\).

Worked Examples

Common Pitfalls and Why the Result Matters

Do not count attachment edges instead of attachment vertices. Suppose an outside component has several edges to the same vertex \(x\in V(H)\). Its attachment set still contains only \(x\). For example, let \(H\) be a triangle on \(\{1,2,3\}\), and let \(G\) add vertices \(a,b\) and edges \(xa,xb,ab\), where \(x=1\). Counting \(1a,1b,ab\) as three attachments would be wrong: the only vertex of \(H\) adjacent to the outside component is \(1\). Moreover, this \(G\) is not 2-connected: deleting \(1\) separates \(a,b\) from \(2,3\). The attachment lemma concerns distinct neighbors in \(H\), and its conclusion depends on 2-connectivity.

Do not select a path that merely has endpoints in \(H\). Its internal vertices must be outside \(H\). In the first worked example, \(1,2,3\) is a path in \(H\), not an ear of \(H\), even though its endpoints lie in \(H\). The path \(1,a,b,c,2\) works because every internal vertex is outside \(H\).

The theorem matters because it lets us grow a 2-connected subgraph in stages: whenever it is still proper, an ear is available, including a one-edge ear when only edges are missing. This existence result is an important step toward describing 2-connected graphs by sequences of ears. The essential reasoning is local: an outside component with only one attachment would create a cut vertex, so it must offer two distinct endpoints for a path through the component.