Open Ears and Ear Decompositions

Building a Graph One Ear at a Time

A graph can sometimes be described more informatively by how it is assembled than by a single list of edges. One useful way to build a graph is to begin with a cycle and then add paths whose endpoints are already present, while the internal vertices of each path are new. These paths are called open ears. They give a precise record of how new parts of a graph attach to what has already been built.

All graphs here are finite and simple. A path \(v_0v_1\cdots v_\ell\) has distinct vertices, with consecutive vertices adjacent; its length is \(\ell\), the number of its edges. For a subgraph \(H\) of a graph \(G\), write \(V(H)\) and \(E(H)\) for its vertex and edge sets. An edge written \(uv\) is the unordered edge between \(u\) and \(v\).

The endpoints of an open ear are its endpoints; the vertices between them are its internal vertices. The condition that the endpoints be distinct matters: a path that starts and ends at the same vertex is not an open ear. Requiring new edges also matters for a length-one ear, because its two endpoints may already be adjacent in \(H\).

At each stage, taking the union adds the ear's edges and its internal vertices; its endpoints are already present. Thus an ear decomposition is more than a list of paths: each path must be valid at the stage when it is added, and together the initial cycle and ears must account for every vertex and edge of the final graph. An ear of length one adds an edge but no vertices.

Counting What Each Ear Adds

The length of an ear immediately records how many edges it contributes. Because a path of length \(\ell\) has \(\ell-1\) internal vertices, and all of those vertices are new at the stage of addition, the same length also determines the vertex increase.

Proof. The initial cycle has \(q\) vertices and \(q\) edges. At stage \(i\), the endpoints of \(P_i\) are already in \(G_{i-1}\). The path has \(\ell_i-1\) internal vertices, all outside \(V(G_{i-1})\), so the number of vertices increases by exactly \(\ell_i-1\). Its \(\ell_i\) edges are new, so the number of edges increases by exactly \(\ell_i\). Applying these increases for every \(i\) gives the two displayed sums. Subtracting the vertex sum from the edge sum gives \[ |E(G)|-|V(G)|=\sum_{i=1}^k\bigl(\ell_i-(\ell_i-1)\bigr)=\sum_{i=1}^k1=k. \] If \(k=0\), the sums are empty and both counts equal \(q\), so the identity still holds. \(\square\)

This identity is a bookkeeping test, not a substitute for checking the decomposition itself. A graph with the right difference between its edge and vertex counts need not have the proposed ears: the endpoints, newness conditions, and complete coverage must still be verified.

Reading a Sequence of Ears

To check a proposed decomposition, inspect the stages in order. At each stage, check that the endpoints are distinct and already present, that every internal vertex is new, and that every ear edge is new. Only after these local checks should you confirm that the final graph has exactly the stated vertices and edges.

A Structural Check on Cycle-Start Decompositions

There is a simple necessary condition that can rule out a proposed cycle-start decomposition. Every vertex in a graph built this way has at least two incident edges. The initial cycle gives each of its vertices two cycle edges; each newly introduced vertex is internal to an ear and has two distinct neighbors along that path. Later steps add edges without deleting any. This condition is useful for checking examples, but it is only a necessary condition here.

Proof. Let \(G_0\) be the initial cycle. Each vertex of \(G_0\) is incident with its two cycle edges, so its degree in \(G_0\) is at least \(2\). Consider any vertex first added at a later stage \(i\). It must be an internal vertex of \(P_i\), since the endpoints of \(P_i\) already belong to \(G_{i-1}\). An internal vertex of a path has a preceding and a following vertex, which are distinct because the path has distinct vertices. The two corresponding edges are distinct, so this vertex has degree at least \(2\) in \(G_i\). No later step deletes vertices or edges, so every vertex has degree at least \(2\) in the final graph. \(\square\)

Common Mistakes and Why the Language Matters

Counting an ear's endpoints as new vertices. An ear path includes both endpoints in its description, but those endpoints already belong to the current graph. For a path of length \(\ell\), the vertex increase is \(\ell-1\), not \(\ell+1\). For example, the path \(1\,4\,5\,2\) has length \(3\): its endpoints \(1,2\) are old, and only \(4,5\) are new. It adds \(2\) vertices and \(3\) edges.

Allowing an endpoint to repeat. The path \(1\,4\,1\) does not qualify as an open ear relative to a graph containing \(1\): its two endpoints coincide. Open ears have distinct endpoints; allowing coincident endpoints changes the definition and describes a different kind of attachment.

Assuming every graph can start with a cycle. Consider the graph with vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,31,14\}\). Vertex \(4\) has degree \(1\), since the only edge incident with it is \(14\). By the proposition, this graph cannot have a cycle-start open ear decomposition. In particular, the edge \(14\) cannot be added as an open ear after a cycle containing \(1\): its other endpoint \(4\) would have to be an internal vertex, but a length-one path has no internal vertices and both endpoints must already be present. The degree check gives the same obstruction. This does not assert a characterization of which graphs have ear decompositions; it is a necessary-condition test.

Ear decompositions matter because they turn a graph into an ordered construction with explicit attachment points. That record lets us track exactly which vertices and edges are present at each stage. In the study of blocks and connectivity, this language supports more advanced results about how paths attach to a graph. Here the key task is more basic: verify the definition at every stage and keep the vertex and edge counts consistent.