Why Block and Ear Arguments Need Careful Hypotheses
Arguments about blocks and ears often turn on a short phrase: “maximal,” “shared vertex,” or “new internal vertices.” Each phrase imposes a precise condition. If it is weakened or misread, a valid local observation can lead to an invalid conclusion—for example, treating two pieces that meet at a cut vertex as one 2-connected piece, or calling a path an ear even though it runs through an old vertex.
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 graph of order at least \(3\) is 2-connected if it is connected and deleting any one vertex leaves a connected graph. A cut vertex of a connected graph is a vertex whose deletion disconnects the graph. A block of order at least \(3\) is a 2-connected subgraph maximal under inclusion among 2-connected subgraphs of the graph. Some conventions also call a bridge together with its endpoints a block, and treat an isolated vertex separately; the results below about 2-connected subgraphs concern blocks of order at least \(3\).
The endpoint and internal-vertex conditions are relative to the current subgraph \(H\), not to the original graph in isolation. When an ear is added, its internal vertices are new to the growing subgraph. A sequence that builds a graph vertex by vertex uses nontrivial ears at each growth step. Some edge-decomposition conventions also allow a trivial ear consisting of one new edge between old vertices; that convention must be stated separately, because such an edge adds no vertices.
Maximality and Shared Vertices
Proof. Let \(B_1\) and \(B_2\) be 2-connected subgraphs with at least two common vertices. Their union is connected because each subgraph is connected and they intersect. We show that deleting any vertex \(x\) leaves their union connected. Each \(B_i-x\) is connected when \(x\in V(B_i)\); when \(x\notin V(B_i)\), the whole \(B_i\) remains connected. Since \(B_1\) and \(B_2\) have at least two common vertices, at least one common vertex remains after deleting \(x\). Thus the two remaining connected subgraphs still intersect, and their union is connected. The union is 2-connected. If \(B_1\) and \(B_2\) were distinct maximal 2-connected subgraphs, this union would strictly contain at least one of them, contradicting maximality. \(\square\)
This proposition is a useful maximality test, but it does not say that any two subgraphs sharing a vertex are parts of a larger block. Nor does it say that an arbitrary subgraph containing vertices from two regions must contain their separating vertex. Connectedness is essential to that latter claim.
Worked Example: Two Triangles Meeting at a Cut Vertex
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,31,34,45,53\}\). The graph consists of the triangles on \(\{1,2,3\}\) and \(\{3,4,5\}\), meeting at vertex \(3\).
Each triangle is 2-connected: deleting any one of its vertices leaves the edge between the other two, which is connected. To check maximality, consider a connected subgraph containing a vertex from \(\{1,2\}\) and a vertex from \(\{4,5\}\). Every path in \(G\) from one side to the other passes through \(3\), so that connected subgraph must contain \(3\). Deleting \(3\) separates its vertices on the two sides. It therefore cannot be 2-connected. This proves that neither triangle can be enlarged to a 2-connected subgraph, so both are blocks.
The connectedness qualification matters. The subgraph on vertices \(\{1,4\}\) with no edges contains vertices from both triangles but does not contain \(3\); it is simply disconnected. Thus the statement about needing \(3\) is true for connected subgraphs, not for arbitrary subgraphs.
Check: In \(G-3\), the remaining edges are \(12\) and \(45\), so the vertices on the two sides lie in separate components. Hence \(3\) is a cut vertex, consistent with the two blocks sharing exactly that one vertex.
Worked Example: Two Smaller 2-Connected Subgraphs That Are Not Blocks
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,24,41\}\). The triangles on \(\{1,2,3\}\) and \(\{1,2,4\}\) are each 2-connected, and they share the two vertices \(1,2\).
The union is the whole graph. It is connected. Deleting \(1\) leaves edges \(23\) and \(24\), which connect all three remaining vertices through \(2\). Deleting \(2\) leaves edges \(31\) and \(41\), which connect all three remaining vertices through \(1\). Deleting \(3\) leaves edges \(12,24,41\), a connected graph; deleting \(4\) leaves the triangle \(1,2,3\), also connected. Thus the union is 2-connected.
Consequently, neither triangle is maximal, so neither is a block. This is exactly the situation ruled out by the proposition: two 2-connected subgraphs sharing at least two vertices can be enlarged together. The proposition does not say they are automatically equal; maximality is what forces that conclusion for blocks.
Check: The union has \(4\) vertices and remains connected after each of the \(4\) possible single-vertex deletions, so it meets the stated definition of 2-connectivity.
Checking Whether a Path Is an Ear
Before using an ear argument, compare every vertex of the path with the current subgraph \(H\). Its endpoints must be distinct vertices already in \(H\). Every internal vertex must be outside \(H\). A path that fails either condition is not an open ear under the definition above, even if adding its edges happens to produce a 2-connected graph.
Proof. Write the path as \(a=v_0,v_1,\ldots,v_k=b\), where \(a\ne b\) are in \(H\), \(k\ge2\), and \(v_1,\ldots,v_{k-1}\) are outside \(H\). The union is connected because \(H\) is connected and \(P\) joins two vertices of \(H\). It remains to check deletion of an arbitrary vertex \(x\).
If \(x\) is an internal vertex of \(P\), then \(H\) remains connected. The two remaining pieces of the path, if both are nonempty, attach to \(a\) and \(b\), respectively, which belong to the connected graph \(H\). Hence the union after deletion is connected. If \(x\in V(H)\), then \(H-x\) is connected. If \(x=a\), the portion of \(P-x\) attaches to \(b\); if \(x=b\), it attaches to \(a\). If \(x\) is another vertex of \(H\), the intact path still attaches at both endpoints. In every case all remaining vertices lie in one connected graph. Thus deleting any vertex leaves \(H\cup P\) connected, proving it is 2-connected. \(\square\)
Worked Example: Verifying a Valid Ear Addition
Let \(H\) have \(V(H)=\{1,2,3\}\) and \(E(H)=\{12,23,31\}\), and let \(P\) be the path \(1,4,5,2\). Its endpoints \(1,2\) are distinct vertices of \(H\), its internal vertices \(4,5\) are outside \(H\), and its edges \(14,45,52\) are not in \(H\). Therefore it is a nontrivial open ear relative to \(H\).
The union has vertex set \(\{1,2,3,4,5\}\) and edge set \(\{12,23,31,14,45,52\}\). The theorem predicts it is 2-connected. Check directly by deleting each vertex:
- Deleting \(1\) leaves edges \(23,45,52\), connecting the vertices by the path \(3,2,5,4\).
- Deleting \(2\) leaves edges \(13,14,45\), connecting the vertices by the path \(3,1,4,5\).
- Deleting \(3\) leaves edges \(12,14,45,52\), a connected cycle on \(1,2,5,4\).
- Deleting \(4\) leaves edges \(12,23,31,52\); vertex \(5\) is joined to \(2\), and \(1,2,3\) form a triangle.
- Deleting \(5\) leaves edges \(12,23,31,14\); vertex \(4\) is joined to \(1\), and \(1,2,3\) form a triangle.
Check: The union is connected before deletion because it contains the triangle and the path attached at \(1,2\). Each of the five deletion checks leaves a connected graph, as required by the definition.
Worked Example: An Endpoint Outside the Current Subgraph
Let \(H\) again be the triangle with \(V(H)=\{1,2,3\}\), \(E(H)=\{12,23,31\}\). Add the path \(1,4,5,6\), so the resulting graph has \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,31,14,45,56\}\).
This path is not an ear relative to \(H\): vertex \(1\) is in \(H\), but endpoint \(6\) is not. Moreover, deleting \(5\) leaves vertex \(6\) isolated while \(1,2,3,4\) remain connected through the triangle and edge \(14\). The resulting graph is not 2-connected. The ear theorem cannot be applied because one endpoint is not an old vertex to which the path attaches.
Check: In the graph after deleting \(5\), the edge \(56\) is gone, and no other edge is incident with \(6\). Thus there are at least two components, directly verifying the failure of 2-connectivity.
Why “New Internal Vertices” Is Not Optional
The internal-vertex condition says more than that the path has some new vertices: all of its internal vertices must be outside the current subgraph. It ensures that an ear really is a new segment joining old endpoints, and that the sequence of subgraphs grows in a controlled way. If a proposed path runs through an old vertex, it is not an ear under this definition. One cannot count that path as a valid ear or invoke a result whose hypothesis requires one.
For example, take the triangle \(H\) with vertices \(\{1,2,3\}\) and edges \(\{12,23,31\}\), and propose the path \(1,4,2,3\). Its endpoints \(1,3\) are in \(H\), but the internal vertex \(2\) is already in \(H\), and the edge \(23\) is already present. So this is not an open ear relative to \(H\). The graph obtained by adding just the new edges \(14,42\) may still be 2-connected; the point is that this particular path does not meet the ear hypothesis. The valid conclusion must come from a valid argument, not merely from an outcome that happens to be true.
There is a related bookkeeping issue. If a process is building a 2-connected subgraph by adding vertices, each nontrivial ear must contribute new internal vertices. Once all vertices are present, an extra edge between old vertices has no new internal vertices. Some edge-decomposition conventions include such an edge as a trivial ear, namely a one-edge path; it is not a nontrivial vertex-adding ear. State which convention is being used before asserting that a list of ears accounts for every edge.
A Practical Audit for Block and Ear Proofs
When a proof claims that a subgraph is a block, check maximality, not just 2-connectivity. A subgraph can be 2-connected without being maximal, as the two triangles sharing an edge demonstrate. To prove maximality, rule out every 2-connected enlargement. In a graph split by a cut vertex, the efficient argument is often to restrict attention to a connected candidate enlargement: any connected subgraph spanning both sides must use the cut vertex, and deleting it separates the sides.
When a proof claims that two blocks combine, check their intersection. If two 2-connected subgraphs share at least two vertices, their union is 2-connected by the proposition, so distinct maximal pieces cannot have that intersection. Sharing exactly one vertex is different: the vertex may be an articulation point, and the pieces need not combine into a 2-connected graph. Do not replace “two common vertices” by “a common vertex” in the union argument; after deleting the one shared vertex, the two pieces may have no connection left.
When a proof adds an ear, write down the current vertex set and test the path against it. Confirm that the endpoints are distinct and already present, that every internal vertex is new, and that the path contributes edges not already present. Only then use the preservation theorem. These checks are short, but they prevent a proof from silently applying a theorem outside its hypotheses.
Common Mistake: Proving Too Much About Arbitrary Subgraphs
In the graph of the two triangles meeting at vertex \(3\), a tempting claim is: “Any subgraph containing vertices from both triangles must contain \(3\).” This is false. The subgraph with vertex set \(\{1,4\}\) and no edges contains vertices from both triangles and omits \(3\).
The correction is to include the needed hypothesis: “Any connected subgraph containing a vertex from \(\{1,2\}\) and a vertex from \(\{4,5\}\) must contain \(3\).” A path between those sides must pass through \(3\), since the listed edge set has no other route between them. Deleting \(3\) then separates the vertices on the two sides. This corrected statement is exactly what is needed to rule out a 2-connected enlargement; the false statement about arbitrary subgraphs is unnecessary.
Check: The counterexample subgraph is disconnected, while every candidate 2-connected enlargement must be connected. The corrected argument therefore applies to the relevant candidates without claiming more than is true.
Check Your Understanding
For each question, identify the exact hypothesis that makes the conclusion valid.
- Why can two distinct maximal 2-connected subgraphs not share two vertices? State what happens to their union after deleting an arbitrary vertex.
- In the graph with edges \(12,23,31,34,45,53\), why is connectedness needed when claiming that a subgraph meeting both triangles contains \(3\)? Give a disconnected counterexample.
- Let \(H\) be a triangle on \(\{a,b,c\}\), and consider the path \(a,x,b\). State the conditions under which it is a nontrivial open ear relative to \(H\).
- Explain why a path with one endpoint outside \(H\) cannot be used in the ear-preservation theorem.
- What is the difference between a nontrivial ear in a vertex-building sequence and a trivial ear sometimes used in an edge-decomposition convention?