= Topological minor
{title2=$H\preccurlyeq_{\mathrm{top}}G$}
A <topological minor> records a network pattern whose <vertices> remain individual junctions but whose <edges> may become longer routes. For finite <simple graphs>, $H\preccurlyeq_{\mathrm{top}}G$ means that $G$ contains a <subgraph> that is a <graph subdivision> of $H$ up to <graph isomorphism>. Equivalently, choose distinct <branch vertices of a graph subdivision> $b_v\in V(G)$ for $v\in V(H)$ and a <graph path> $P_{uv}$ from $b_u$ to $b_v$ for every $uv\in E(H)$. These are <internally vertex-disjoint paths>, and no internal <vertex> of any $P_{uv}$ is a <branch vertex of a graph subdivision>. Only endpoints corresponding to a shared target <vertex> may be shared.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>[§1.7, printed p. 18: subdivisions; printed p. 21: topological-minor embeddings]{ref}
The <graph subdivision> example below replaces two <edges> of a <triangle in a graph> by routes of two and three <edges> while retaining its attached <leaf of a graph>. If the host <graph> also contains an extra <edge> $BD$, the same routes still witness a <topological minor>: delete $BD$ when selecting the <subgraph>. An <induced subgraph> is not required. However, routes that merely connect the right pairs are insufficient: using a <branch vertex of a graph subdivision> as an intermediate junction, or making two routes share an internal <vertex>, can change the local network structure.
Every <topological minor> is a <graph minor>. In each <branch path of a graph subdivision>, contract all but one <edge>; the disjoint interiors let this shorten each route without merging distinct <branch vertices of a graph subdivision>. This recovers $H$ after deleting unused <vertices> and <edges>.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>[Proposition 1.7.3(i), printed p. 21]{ref} The converse fails because an ordinary <branch set of a graph minor> can gather several junctions into one.
For the <tree> $T$ with <vertices> $u,v,a,b,c,d$ and <edges> $uv,ua,ub,vc,vd$, contracting $uv$ produces a <star graph> $K_{1,4}$: the <branch sets of a graph minor> are $\{u,v\},\{a\},\{b\},\{c\},\{d\}$. Both $u,v$ have <degree of a vertex> three; each of the other four <vertices> is a <leaf of a graph> with <degree of a vertex> one. The new centre $w$ has four distinct <graph neighbours> $a,b,c,d$; its <degree of a vertex> is $3+3-2=4$, in agreement with the <edge contraction> formula.
\Image[/topological-minor-tree-contraction-degree-obstruction.png]
{title=A <graph minor> can combine two junctions: contracting $uv$ creates a <star graph> with a centre of <degree of a vertex> four}
Yet $K_{1,4}$ is not a <topological minor> of $T$. In a <graph subdivision> of $K_{1,4}$, four <branch paths of a graph subdivision> must leave the centre through four different <edges>; sharing their first internal <vertex> would violate internal disjointness. Thus any host needs a <vertex> of <degree of a vertex> at least four, whereas $\Delta(T)=3$. More generally, $H\preccurlyeq_{\mathrm{top}}G$ implies $\Delta(H)\leq\Delta(G)$, where $\Delta$ is the <maximum degree of a graph>. This bound concerns the host <graph>; extra unused <edges> may make its <branch vertices of a graph subdivision> have larger <degrees of vertices> than their target counterparts.
This distinction matters when a network's individual junctions have a limited number of connections: replacing a connection by a route preserves the number of routes meeting at each chosen junction, while contracting a connected region can combine connections from separate junctions. It also explains why a small nonplanar pattern can hide inside long routes. By <Kuratowski's theorem>, a finite <simple graph> is a <planar graph> exactly when it has neither the <complete graph> $K_5$ nor the <complete bipartite graph> $K_{3,3}$ as a <topological minor>. The obstruction is a <graph subdivision> inside the network, regardless of the number of intermediate <vertices>.
Back to article page
