Replacing Edges by Paths
In planar graph arguments, a graph may appear with some of its edges stretched into longer routes. The intermediate vertices change the graph’s order and size, but the pattern of connections between the original vertices is retained. Subdivision gives a precise language for this operation. Homeomorphic graphs are graphs that become isomorphic after such edge-stretching, even when the graphs as originally given have different numbers of vertices.
Throughout, graphs are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent; its length is its number of edges. The internal vertices of a path are all its vertices except its two endpoints. Paths are internally disjoint when no internal vertex of one is an internal vertex of another. When discussing a particular collection of paths, we will also require their interiors to avoid all specified original vertices.
Thus each edge of the original graph has one corresponding replacement path. Two such paths can share a branch vertex precisely when their original edges share the corresponding endpoint. They cannot share internal vertices, and there are no additional edges in the subdivision. If \(B\) has an isolated vertex, its corresponding branch vertex remains isolated. If \(B\) has no vertices, its subdivision is also the empty graph.
A graph \(H\) contains a subdivision of \(B\) if some subgraph of \(H\) is a subdivision of \(B\). A subgraph may omit vertices or edges of \(H\); it need not be induced. Two graphs are isomorphic if there is a bijection between their vertex sets that preserves adjacency in both directions.
Reading a Subdivision from Its Paths
To verify that a graph contains a subdivision, specify the original vertices, give one replacement path for every original edge, and check that the paths have the required interiors. The edge list of the subgraph should consist exactly of the edges on those paths. This last check prevents accidentally treating extra edges as part of the subdivision.
Worked Example: A Subdivision of \(K_4\)
Let \(B=K_4\), with \(V(B)=\{1,2,3,4\}\) and \(E(B)=\{12,13,14,23,24,34\}\). Define \(H\) by \(V(H)=\{1,2,3,4,a,b,c\}\) and \(E(H)=\{1a,a2,13,14,23,24,3b,bc,c4\}\).
Use \(1,2,3,4\) as the branch vertices. The six replacement paths, in the order of the six edges of \(B\), are \(1,a,2\) for \(12\); the single edges \(1,3\), \(1,4\), \(2,3\), and \(2,4\) for \(13,14,23,24\); and \(3,b,c,4\) for \(34\). The interiors are \(\{a\}\) and \(\{b,c\}\) for the two longer paths, and empty for the single-edge paths. These interiors are disjoint and contain no branch vertex. Their path edges give exactly the listed edge set of \(H\), so \(H\) is a subdivision of \(K_4\).
Check: \(H\) has \(7\) vertices and \(9\) edges. The two replacement paths of lengths \(2\) and \(3\), together with four paths of length \(1\), account for \(2+3+1+1+1+1=9\) edges. The degrees in \(H\) are \(3,3,3,3,2,2,2\) at \(1,2,3,4,a,b,c\), respectively; their sum is \(18=2\cdot9\). In particular, each branch vertex has the same degree here as its corresponding vertex in \(K_4\).
A subdivision can sit inside a larger graph without being an induced subgraph. The definition asks for a subgraph with the required replacement paths, not for every edge of the larger graph between selected vertices to be included.
Worked Example: Finding a Subdivision of \(K_{3,3}\)
Let \(B=K_{3,3}\), with parts \(\{u_1,u_2,u_3\}\) and \(\{v_1,v_2,v_3\}\), and all nine edges \(u_iv_j\). Define \(H\) on \(V(H)=\{u_1,u_2,u_3,v_1,v_2,v_3,x,y,z,w\}\). Its edges are the seven single edges \(\{u_1v_2,u_1v_3,u_2v_1,u_2v_2,u_3v_1,u_3v_2,u_3v_3\}\), together with \(u_1x,xv_1,u_2y,yz,zv_3,u_1w\).
Take \(u_1,u_2,u_3,v_1,v_2,v_3\) as branch vertices. The replacement paths for the nine edges of \(K_{3,3}\) are \(u_1,x,v_1\) for \(u_1v_1\), \(u_2,y,z,v_3\) for \(u_2v_3\), and the seven listed single-edge paths for the other seven edges. The path interiors are \(\{x\}\), \(\{y,z\}\), and seven empty sets, so they are pairwise disjoint and avoid all branch vertices. The extra edge \(u_1w\) is not used. Removing \(w\) and that edge leaves exactly the edges of the replacement paths, so this subgraph is a subdivision of \(K_{3,3}\).
Check: \(H\) has \(10\) vertices. Its seven single-edge paths contribute \(7\) edges, and the two longer paths contribute \(2+3=5\), for \(12\) edges in the subdivision; the extra edge \(u_1w\) makes \(13\) edges in \(H\). The degrees in \(H\), in the vertex order displayed, are \(4,3,3,3,3,3,2,2,2,1\), with sum \(26=2\cdot13\). This also confirms the edge count independently by the handshake lemma.
Common Refinements
To prove that homeomorphism is transitive, it is not enough to assume two subdivisions of the same graph are isomorphic. Their replacement paths can have different lengths, so their vertex counts can differ. Instead, the key fact is that two subdivisions of one graph can be further subdivided until they are isomorphic.
Proof. Fix the subdivision representation of each graph using \(B\). For every edge \(e\in E(B)\), let \(a_e\) be the length of its replacement path in \(B_1\), and let \(b_e\) be the length of its replacement path in \(B_2\). Both are positive integers. Choose \(L_e=\max(a_e,b_e)\). In the representation of \(B_1\), subdivide edges along the path for \(e\) enough times to increase its length from \(a_e\) to \(L_e\); this is possible by inserting \(L_e-a_e\) vertices into its edges. Do the same in \(B_2\), inserting \(L_e-b_e\) vertices along its path for \(e\). If either difference is zero, that path needs no further subdivision. The resulting paths for each \(e\) have equal lengths in the two graphs, and paths belonging to different edges still have disjoint interiors. Map the branch vertex corresponding to each vertex of \(B\) to its counterpart, and map the internal vertices of each pair of paths in order from one endpoint to the other. This is a bijection preserving adjacency in both directions, since the graphs consist exactly of these paths and their branch vertices. The further subdivisions are therefore isomorphic. \(\square\)
Proof. Suppose a graph \(B_1\) is a subdivision of \(B\), with one replacement path in \(B_1\) for each edge of \(B\). Now subdivide edges of \(B_1\). Each edge of \(B_1\) lies on the replacement path for exactly one edge of \(B\). Replacing that edge by a path therefore lengthens that replacement path, leaving its endpoints unchanged. Repeating this for any selected edges gives, for every edge of \(B\), a path with the same endpoints as before. No new internal vertex is shared between paths, because each new vertex belongs to the particular edge being subdivided, and the original replacement paths had disjoint interiors. The resulting graph still consists exactly of the replacement paths and the branch vertices. It is a subdivision of \(B\). \(\square\)
Worked Example: Different Subdivisions, One Homeomorphism Class
Let \(B=K_2\), with \(V(B)=\{p,q\}\) and \(E(B)=\{pq\}\). Let \(B_1\) be \(K_2\) itself, so \(V(B_1)=\{p,q\}\) and \(E(B_1)=\{pq\}\). Let \(B_2=P_3\), with \(V(B_2)=\{r,s,t\}\) and \(E(B_2)=\{rs,st\}\). Both are subdivisions of \(K_2\): their replacement paths have lengths \(1\) and \(2\), respectively.
They are not isomorphic, since \(B_1\) has \(2\) vertices and \(B_2\) has \(3\). Refine each to a path of length \(3\). In \(B_1\), replace \(pq\) by \(p,a,b,q\), giving vertices \(\{p,a,b,q\}\) and edges \(\{pa,ab,bq\}\). In \(B_2\), subdivide \(rs\), giving vertices \(\{r,x,s,t\}\) and edges \(\{rx,xs,st\}\). The map \(p\mapsto r,\ a\mapsto x,\ b\mapsto s,\ q\mapsto t\) is an isomorphism between these refinements: it takes \(pa,ab,bq\) to \(rx,xs,st\).
Check: each refined graph has \(4\) vertices and \(3\) edges, with degree sequence \(1,2,2,1\). The original graphs have different orders, so they are not isomorphic; their common refinements demonstrate directly that they are homeomorphic.
Homeomorphism Is an Equivalence Relation
Proof. For reflexivity, any graph is a subdivision of itself by taking every replacement path to be the original edge, of length \(1\). Thus a graph has a subdivision isomorphic to itself. For symmetry, if a subdivision of \(G\) is isomorphic to a subdivision of \(H\), the inverse isomorphism shows that a subdivision of \(H\) is isomorphic to a subdivision of \(G\).
For transitivity, suppose \(G\) is homeomorphic to \(H\), and \(H\) is homeomorphic to \(J\). Choose subdivisions \(G_1\) of \(G\) and \(H_1\) of \(H\) that are isomorphic, and subdivisions \(H_2\) of \(H\) and \(J_1\) of \(J\) that are isomorphic. Use these representations to identify the branch vertices of \(H_1\) and \(H_2\) with the corresponding vertices of \(H\). No isomorphism between \(H_1\) and \(H_2\) is assumed or needed. By the lemma, further subdivisions of \(H_1\) and \(H_2\) can be made isomorphic. Carry the subdivisions of \(H_1\) across its isomorphism with \(G_1\), and carry the subdivisions of \(H_2\) across its isomorphism with \(J_1\). The resulting graphs are isomorphic, and each is a subdivision of its original graph by the proposition. Hence \(G\) and \(J\) are homeomorphic. This proves transitivity. \(\square\)
Why the Path Conditions Matter
The replacement-path definition records the structure that homeomorphism preserves. It is not enough to select a collection of paths with the right endpoints: their interiors must be disjoint, must avoid the branch vertices, and the chosen subgraph must have no extra edges beyond those on the paths. An isolated vertex of the original graph must also be represented; it cannot be silently omitted just because it is not on an edge.
Common mistake: assuming subdivisions of one graph are isomorphic. For \(K_2\), the graph with one edge is a subdivision of \(K_2\), and so is \(P_3\). Their orders are \(2\) and \(3\), so they cannot be isomorphic. The correction is to use the paths in each subdivision representation to match the original vertices, then lengthen corresponding replacement paths until their lengths agree. The resulting refinements are isomorphic, as in the worked example.
Subdivision and homeomorphism are useful because they separate a graph’s connection pattern from the number of degree-two intermediate vertices placed along its edges. When identifying a particular subdivision, however, always verify the actual path representation rather than relying only on a visual impression of the graph.
Check Your Understanding
For each question, state the relevant vertices, edges or paths precisely.
- Let \(B\) have vertices \(\{1,2,3\}\) and edges \(\{12,23\}\). Give a graph that is a subdivision of \(B\) in which the replacement path for \(12\) has length \(3\) and the replacement path for \(23\) has length \(1\).
- Why must the interiors of replacement paths be disjoint in the definition of a subdivision?
- Can a graph with \(2\) vertices be isomorphic to a subdivision of \(K_2\) with a replacement path of length \(3\)? Explain using vertex counts.
- In the \(K_{3,3}\) example, which edge is not part of the displayed subdivision, and why does its presence in the larger graph not invalidate the example?
- Explain how to make two subdivisions of the same graph isomorphic when their corresponding replacement paths have different lengths.