Branch Vertices Mark the Underlying Graph
A subdivision replaces edges by paths: the original endpoints remain, while additional vertices are inserted inside the paths. When the graph being subdivided has minimum degree at least three, those original vertices can be recognized within the subdivision: they have degree at least three, while every inserted vertex has degree two. This gives a practical way to recover the original graph, provided the subdivision under consideration is specified.
All graphs in this tutorial are finite and simple. A subgraph need not be induced. A path has distinct vertices, with consecutive vertices adjacent. If an edge \(uv\) of a graph \(H\) is replaced by a \(u\)-\(v\) path, the internal vertices of that path are all vertices other than its endpoints. A subdivision of \(H\) is obtained by replacing each edge of \(H\) by a path of positive length, with distinct replacement paths internally vertex-disjoint and with no internal vertex equal to a vertex of \(H\). A path of length one leaves its edge unchanged.
The minimum-degree hypothesis matters. If \(H\) has vertices of degree one or two, their images in a subdivision also have degree one or two, so degree alone does not identify all original vertices. There is another exception when a whole component is a cycle: all its vertices have degree two, and the graph itself supplies no distinguished branch vertices. Thus the degree test is a precise recovery method under stated hypotheses, not a way to identify every possible presentation of every graph.
Suppressing Degree-Two Vertices
Suppression reverses the operation of inserting a vertex into an edge. In the setting of a specified subdivision, it is applied to internal vertices of its replacement paths. If \(x\) is such a vertex, it has two neighbors \(u\) and \(v\) on that path; remove \(x\) and the edges \(ux,xv\), and replace that two-edge segment by \(uv\). The resulting graph is still a subdivision of the same underlying graph, with that path shortened by one edge.
This rule is deliberately stated for a specified subdivision. In a general simple graph, suppressing an arbitrary degree-two vertex can create an edge that is already present, in which case the result would have parallel edges. That situation does not arise when shortening the paths of a subdivision of a simple graph: a direct edge between the same original endpoints in addition to a distinct replacement path would represent two edges of the underlying graph with the same endpoints. The recovery process should therefore be applied to the selected subdivision paths, not indiscriminately to every degree-two vertex in a larger ambient graph.
Worked Example: Recovering a Subdivision of \(K_4\)
Let \(G\) have vertex set \(\{a,b,c,d,p,q,r\}\) and edge set \(\{ap,pb,ac,ad,bc,bd,cq,qr,rd\}\). This is a subdivision of \(K_4\): the edge \(ab\) is replaced by \(a,p,b\), the edge \(cd\) by \(c,q,r,d\), and the other four edges are unchanged.
The degrees are \(\deg(a)=3\), from \(ap,ac,ad\); \(\deg(b)=3\), from \(pb,bc,bd\); \(\deg(c)=3\), from \(ac,bc,cq\); and \(\deg(d)=3\), from \(ad,bd,rd\). Also, \(\deg(p)=2\), \(\deg(q)=2\), and \(\deg(r)=2\). Thus the branch vertices are \(a,b,c,d\).
Suppress \(p\), whose neighbors are \(a,b\). The two edges \(ap,pb\) are replaced by \(ab\). Next suppress \(q\), replacing \(cq,qr\) by \(cr\); then suppress \(r\), whose current neighbors are \(c,d\), replacing \(cr,rd\) by \(cd\).
| Stage | Edges after suppression |
|---|---|
| Start | \(ap,pb,ac,ad,bc,bd,cq,qr,rd\) |
| Suppress \(p\) | \(ab,ac,ad,bc,bd,cq,qr,rd\) |
| Suppress \(q\) | \(ab,ac,ad,bc,bd,cr,rd\) |
| Suppress \(r\) | \(ab,ac,ad,bc,bd,cd\) |
The final graph has all six edges between the four branch vertices, so it is \(K_4\). Check: the original paths had lengths \(2,1,1,1,1,3\), which sum to \(9=|E(G)|\). Their internal-vertex counts sum to \(1+0+0+0+0+2=3\), giving \(4+3=7=|V(G)|\). Suppression removes three vertices and three edges, leaving \(4\) vertices and \(6\) edges, as in the recovered \(K_4\).
Why Recovery Works
Proof. Consider a vertex \(v\) of \(H\). For each edge incident with \(v\), its replacement path has exactly one edge incident with the copy of \(v\). Therefore the copy of \(v\) in \(S\) has degree \(\deg_H(v)\), which is at least three. Every vertex inserted inside a replacement path has exactly two incident path edges and no other incident edges, so its degree in \(S\) is two. This proves that the vertices of degree at least three in \(S\) are precisely the copies of the vertices of \(H\). Now consider one edge \(uv\) of \(H\), replaced by a path from the copy of \(u\) to the copy of \(v\). Suppressing its internal vertices shortens this path one edge at a time until it is the single edge \(uv\). Applying this to each replacement path restores exactly one edge for each edge of \(H\), with the same endpoints. Hence the recovered graph is \(H\), up to vertex names. \(\square\)
There is also a useful count. If the edges of \(H\) are replaced by paths of lengths \(\ell_e\), one for each \(e\in E(H)\), then the subdivision has \(\sum_{e\in E(H)}\ell_e\) edges. The number of inserted vertices is \(\sum_{e\in E(H)}(\ell_e-1)\), since a path of length \(\ell_e\) has \(\ell_e-1\) internal vertices.
Proof. Each replacement path contributes \(\ell_e\) edges, and the replacement paths partition the edges of the subdivision, so their edge counts add. The same path contributes \(\ell_e-1\) internal vertices. Internal vertices from distinct replacement paths are disjoint, so these counts also add. Suppression removes one internal vertex and one edge each time a path is shortened by one edge. After all internal vertices have been removed, the counts are \(|E(H)|\) edges and \(|V(H)|\) vertices. \(\square\)
Worked Example: Checking the Counts on a Subdivided Triangle
Let \(H\) have vertex set \(\{A,B,C\}\) and edge set \(\{AB,BC,CA\}\). Replace \(AB\) by \(A,x,B\), leave \(BC\) unchanged, and replace \(CA\) by \(C,y,z,A\). The resulting graph \(S\) has vertex set \(\{A,B,C,x,y,z\}\) and edge set \(\{Ax,xB,BC,Cy,yz,zA\}\).
The replacement-path lengths are \(2,1,3\). The edge count is \(2+1+3=6\), matching the six listed edges. The internal-vertex count is \((2-1)+(1-1)+(3-1)=1+0+2=3\), matching \(x,y,z\). Suppress \(x\) to replace \(Ax,xB\) by \(AB\). Suppress \(y\) to replace \(Cy,yz\) by \(Cz\), then suppress \(z\) to replace \(Cz,zA\) by \(CA\). The final edge set is \(\{AB,BC,CA\}\), so the result is \(H\).
Check: the original graph has \(6\) vertices and \(6\) edges. Three suppressions leave \(6-3=3\) vertices and \(6-3=3\) edges, which agrees with the triangle \(H\).
Why the Specified Subgraph Matters
The theorem recovers the underlying graph from a specified subdivision satisfying its hypotheses. It does not say that an arbitrary ambient graph has just one subgraph that can be interpreted as a subdivision, or that an unmarked graph tells us which subgraph was intended. Different choices of subgraph can give different recovered graphs.
Worked Example: Two Different Choices Inside the Same Graph
Let the ambient graph \(G\) have vertex set \(\{1,2,3,4,5\}\) and edge set \(\{12,13,14,15,23,24,25,34,35,45\}\). This is \(K_5\). One specified subgraph \(S_1\) is the whole graph \(G\), which is a subdivision of \(K_5\) with no edges further subdivided. Its five vertices all have degree four, so suppressing degree-two vertices changes nothing and recovers \(K_5\).
A different specified subgraph \(S_2\) has vertex set \(\{1,2,3,4\}\) and edge set \(\{12,13,14,23,24,34\}\). It is \(K_4\), and is a subdivision of \(K_4\) with no edges further subdivided. Its four vertices all have degree three within \(S_2\), so suppression again changes nothing, and this choice recovers \(K_4\). The degrees used here are degrees in the selected subgraph, not in the ambient \(K_5\).
Check: \(S_1\) has \(\binom{5}{2}=10\) edges, and \(S_2\) has \(\binom{4}{2}=6\) edges, matching their explicit edge sets. The same ambient graph therefore contains specified subdivisions with different underlying graphs. Without the choice of subgraph, there is no single intended recovery.
A cycle illustrates a separate limitation of relying only on degree. Let \(C\) have vertex set \(\{1,2,3,4,5\}\) and edge set \(\{12,23,34,45,51\}\). It can be viewed as a subdivision of a triangle by taking triangle vertices \(1,3,5\), replacing edge \(13\) by the path \(1,2,3\), replacing edge \(35\) by \(3,4,5\), and leaving edge \(51\) unchanged. The lengths are \(2,2,1\), so their sum is \(5\). It can also be viewed as a subdivision of itself with no edges subdivided.
These are different presentations, and every vertex of \(C\) has degree two. There are no degree-at-least-three branch vertices to mark. Suppressing a chosen degree-two vertex in a cycle shortens the cycle, but the graph supplies no distinguished endpoints or paths to tell us where to stop. This case is outside the theorem's minimum-degree hypothesis.
Common Pitfalls
Counting replacement lengths incorrectly. Replacing all three edges of a triangle by paths of length two produces a cycle of length \(2+2+2=6\), not a 5-cycle. For the 5-cycle above, the correct lengths are \(2,2,1\), which sum to \(5\). Always add the specified path lengths before identifying the resulting graph.
Using degrees from the ambient graph. A vertex may have extra incident edges outside the selected subdivision. Branch vertices are identified using degrees within the specified subgraph, not automatically by their degrees in the larger graph.
Assuming all degree-two vertices are internal subdivision vertices. That conclusion is valid in a specified subdivision of a graph with minimum degree at least three. It need not be valid for an arbitrary graph, especially a cycle or a graph with an unspecified subgraph.
Check Your Understanding
For each question, state any assumptions needed for the degree test or suppression to apply.
- In a specified subdivision of a graph with minimum degree at least three, why does an original vertex of degree four still have degree four?
- A replacement path has length \(5\). How many internal vertices does it contribute, and how many suppressions shorten it to one edge?
- Give a reason that degree alone may fail to identify original vertices if the underlying graph has a vertex of degree two.
- For the cycle with edge set \(\{12,23,34,45,51\}\), specify three triangle vertices and the three replacement-path lengths that give this 5-cycle.
- Why must the selected subgraph be specified when recovering an underlying graph from a larger ambient graph?