= Graph minor
{title2=$H\preccurlyeq G$}
{wiki}
A <graph minor> compresses connected regions of a <graph> into single <vertices> while retaining selected connections between them. For finite <simple graphs>, $H\preccurlyeq G$ means that some sequence of deleting <vertices>, deleting <edges>, and performing <edge contractions> produces $H$ up to <graph isomorphism>. Deleting a <vertex> also deletes all its incident <edges>; deleting an <edge> leaves its endpoints. The <edge contraction> convention here removes resulting <self-loops> and duplicate <edges>.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>{ref}
For an exact small example, let $G$ be the <cycle graph> $C_4$ with <vertices> $u,v,a,b$ and <edges> $uv,va,ab,bu$. Contract $uv$ to a new <vertex> $w$. The surviving <edges> are $wa,ab,bw$, giving the <complete graph> $K_3$. Thus $K_3\preccurlyeq C_4$, although $C_4$ has no <triangle in a graph> as a <subgraph>. The <branch sets of a graph minor> are $\{u,v\},\{a\},\{b\}$, with the original <edges> $va,ab,bu$ witnessing all three required adjacencies. The first panel of the <edge contraction> diagram shows this operation.
A <subgraph> uses existing <vertices> and <edges>; a <topological minor> permits a <graph subdivision> of the target as a <subgraph>, so target <edges> become <graph paths> with mutually disjoint interiors and no target <vertex> in an interior. An ordinary <graph minor> permits whole connected <branch sets of a graph minor> in place of target <vertices>. Every <topological minor> is a <graph minor>, by contracting the replacement <graph paths>.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>[Proposition 1.7.3(i)]{ref}
The converse fails. Take the <tree> with <edges> $uv,ua,ub,vc,vd$. Contracting $uv$ gives the <star graph> $K_{1,4}$. Yet the original <tree> has <maximum degree> three, whereas every <graph subdivision> of $K_{1,4}$ retains a centre of <degree of a vertex> four. Hence $K_{1,4}$ is a <graph minor> but not a <topological minor> of this <tree>. The difference is that a connected <branch set of a graph minor> may gather connections incident to several original <vertices>.
The counts of <vertices> and <edges> never increase under these operations. However, the $C_4$ example shows that being a <bipartite graph> is not preserved: its <graph minor> $K_3$ contains an <odd cycle>. Its <chromatic number> also increases from two to three. A <connected graph> stays connected under an <edge contraction>, because the image of each <graph path> still connects its endpoints, but deletion can disconnect it. Thus one must check the particular <graph property> before treating it as preserved by taking <graph minors>.
Being a <planar graph> is preserved: in a crossing-free drawing, shrink a contracted <edge> and bring its incident <edges> into the merged <vertex>; deletion merely removes parts of the drawing. This makes a nonplanar <graph minor> a certificate that the original <graph> is nonplanar. More strongly, for a finite <simple graph>, being a <planar graph> is equivalent to having neither the <complete graph> $K_5$ nor the <complete bipartite graph> $K_{3,3}$ as a <graph minor>. Finding the corresponding <branch sets of a graph minor> settles nonplanarity even when no literal $K_5$ or $K_{3,3}$ <subgraph> is present. The converse is a substantial theorem, rather than a consequence of preservation alone.<Graph Theory by Reinhard Diestel/Planar Graphs (author-hosted chapter preview)>[Theorem 4.4.6, equivalence of planarity and exclusion of K5 and K3,3 minors]{ref}
Back to article page
