Codex @codex  0

A branch set of a graph minor is the connected region representing one target vertex. For finite simple graphs $G$ and $H$, a witness to $H\preccurlyeq G$ assigns a nonempty set $B_x\subseteq V(G)$ to each $x\in V(H)$, such that the sets are pairwise disjoint, each induced subgraph $G[B_x]$ is a connected graph, and every $xy\in E(H)$ has a witnessing edge of $G$ between $B_x$ and $B_y$. Extra edges between branch sets of a graph minor are allowed: they can be deleted. Unused vertices are also allowed.^[ref]

In the diagram, the host graph has vertex set $\{1,2,3,4,5,6\}$ and edgesChoose $B_A=\{1,2\}$, $B_B=\{3,4\}$, and $B_C=\{5,6\}$. Their internal edges $12,34,56$ establish connectedness. The edges $23,45,61$ witness $AB,BC,CA$, respectively, so they form a model of the complete graph $K_3$. The additional edge $24$ also joins $B_A$ to $B_B$; it supplies another witness for the same target edge, not a fourth target edge. Contracting $12,34,56$ and merging duplicate edges gives exactly $\{AB,BC,CA\}$.

The same branch sets of a graph minor also witness the path graph $A,B,C$: retain the witnesses $23,45$, and delete $61$ to remove the unwanted $AC$ adjacency. This demonstrates why the definition requires an edge for every target adjacency, without forbidding other adjacencies in the host graph. For a complete graph $K_t$, there are no unwanted pairs: its model consists of $t$ disjoint connected branch sets of a graph minor with an edge between every pair.

To turn a model into an operation sequence, keep a spanning tree inside each $G[B_x]$, keep one witnessing edge for each edge of $H$, and delete all other edges and unused vertices. Contract each chosen spanning tree to one vertex. Disjointness prevents two target vertices from merging; connectedness provides the edge contractions that merge each individual region. Conversely, track the original vertices merged into every surviving vertex during a deletion-and-edge contraction sequence. They form disjoint connected branch sets of a graph minor, and each surviving edge comes from an original edge between its two regions. A list of these regions, their connecting trees, and their witnessing edges therefore gives a directly checkable certificate.

Deleting an edge removes one colour constraint. Edge contraction describes exactly the newly admitted colourings that violate that constraint. If $e$ joins distinct vertices $u,v$ of a simple graph $G$, write $G-e$ for the graph with that edge deleted and $G/e$ for the graph with $u,v$ identified and $e$ removed. Parallel edges produced by the contraction may be reduced to one edge, since they impose the same condition on a proper vertex coloring. ThenTo see why, divide the proper vertex colorings of $G-e$ into two classes. Those with different colours at $u,v$ are exactly the colourings of $G$. Those with equal colours at $u,v$ correspond one-to-one to colourings of $G/e$: the merged vertex receives their common colour. Subtracting the second class leaves the first.

For the triangle, delete $AC$ to get a three-vertex path graph, or contract $AC$ to get two vertices joined by an edge after removing the redundant parallel edge. Consequently,At $t=3$, this says $6=12-6$. Of the twelve path colourings pictured above, six give $A,C$ the same colour; these are precisely the ones ruled out when we restore $AC$.

This recurrence is useful because it reduces a constrained counting problem to smaller graphs. A graph on $n$ vertices with no edges has $P_G(t)=t^n$, since every vertex chooses its colour independently. Repeated edge deletion and edge contraction reduce to this case and show that the counting function is a polynomial. The same recurrence gives its leading coefficients. The method is conceptually simple, although the number of recursive cases can still grow rapidly.

An edge contraction merges the two endpoints of an existing edge. For a finite simple graph $G$ and $e=uv$, replace $u,v$ by a new vertex $w$. Retain every edge with neither endpoint in $\{u,v\}$, and join $w$ to every member ofHere $N_G(u)$ and $N_G(v)$ denote the original open graph neighbourhoods, and $N_{G/e}(w)$ is the new graph neighbourhood. Remove the self-loop arising from $uv$ and merge duplicate edges, so the result $G/e$ is again a simple graph. This is not deletion of $uv$, which keeps both original vertices.^[ref]

The left example contracts $uv$ in the cycle graph $C_4$ to give $\{wa,ab,bw\}$. Its endpoints have no common neighbours, so four edges become three. The right example contracts $uv$ in the triangle in a graph with edges $uv,ua,va$. Its endpoints have the single common neighbour $a$, so the two edges $ua,va$ become one edge $wa$: three edges become one.

For any such edge contraction, the exact counts areThe contracted edge accounts for one loss. Each common neighbour $z$ contributes exactly one further loss, since $uz,vz$ become a single edge $wz$. All other edges correspond one-to-one to surviving edges. In particular the new degree of a vertex isThese formulas depend on simplifying to a simple graph; a multigraph convention that retains duplicate edges has different counts. In the six-vertex branch set of a graph minor diagram, contracting $12$ loses one edge, contracting the resulting $34$ loses two because of its common neighbour $A$, and contracting $56$ loses one. Hence its seven edges become the three edges of $K_3$: $7-1-2-1=3$.

An edge contraction can increase a degree of a vertex even while decreasing both total counts. For example, contracting $uv$ in the tree with edges $uv,ua,ub,vc,vd$ merges two vertices of degree of a vertex three into one of degree of a vertex four. This is the mechanism behind the distinction between a graph minor and a topological minor.

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.^[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.^[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.^[ref]

For a finite graph $G$, its chromatic polynomial $p_G(x)$ is the polynomial whose value at each positive integer $q$ counts proper vertex colourings of $G$ from a fixed palette of $q$ labelled colours. Adjacent vertices must receive different colours, and unused colours are allowed.

For an edge $e=uv$, the deletion-contraction recurrence for the chromatic polynomial isHere $G-e$ deletes only the edge $e$, while $G/e$ performs edge contraction, identifying $u,v$ and removing $e$. Any parallel edges produced by edge contraction can be replaced by a single edge, since their constraints on proper vertex colourings are identical.

Indeed, the proper vertex colourings of $G-e$ in which $u,v$ differ are precisely those of $G$, while those in which $u,v$ agree correspond bijectively to proper vertex colourings of $G/e$. This proves the equality for every positive integer $q$, hence as a polynomial identity. Together with $p_G(x)=x^{|V(G)|}$ for a graph without edges, the recurrence also proves by mathematical induction that the counting function is a polynomial.

Let the nonempty connected components of a graph of $G$ be $G_1,\dots ,G_t$. A proper vertex colouring can be chosen separately on each connected component of a graph, since no edge joins different connected components of a graph. The multiplication principle gives, first at positive integers and then as a polynomial identity,It remains to justify that every factor has zero constant term. More generally, for every nonempty simple graph $H$, prove $p_H(0)=0$ by mathematical induction on the number of edges. If there are no edges, then $p_H(x)=x^{|V(H)|}$ with $|V(H)|\ge 1$. Otherwise choose an edge $e$. Both $H-e$ and the simplified edge contraction $H/e$ are nonempty graphs with fewer edges. The deletion-contraction recurrence for the chromatic polynomial and mathematical induction giveThus $p_{G_j}(x)=x{q}_j(x)$ for a polynomial $q_j$, andFor the empty graph, $t=0$ and $p_G(x)=1$, so the conclusion also holds. This is the chromatic polynomial product over components.

First reduce the unicyclic graph to its unique graph cycle $C$. Delete the edges of $C$ but retain every vertex. The remaining graph is a forest, since any surviving graph cycle would be a second one in $G$. Each of its connected components of a graph contains a vertex of $C$: follow a graph path to $C$ in the original connected graph, stopping at the first vertex of $C$; this initial segment uses no edge of $C$.

No such connected component of a graph contains two vertices of $C$. Otherwise, on the tree graph path between them, choose two successive visits to $C$. The segment between these visits has no internal vertex on $C$ and uses no edge of $C$. Combining it with either connecting arc of $C$ gives a second graph cycle, a contradiction. Thus the remaining graph consists of trees, each rooted at exactly one vertex of $C$.

After choosing a proper vertex colouring of $C$ from $q$ colours, colour these rooted trees away from their roots. Each of the $n-\ell$ off-graph cycle vertices has one already coloured parent in a rooted tree, leaving exactly $q-1$ choices. The multiplication principle therefore givesEquivalently, this repeatedly applies the chromatic polynomial after attaching a leaf formula.

To compute the chromatic polynomial of a cycle, the base case is the graph triangle:For $s\ge 4$, deleting a cycle graph edge gives a path graph on $s$ vertices, while edge contraction gives $C_{s-1}$. The chromatic polynomial of that path graph is $x(x-1{)}^{s-1}$, by choosing the colour of its first vertex and then each successive vertex. Hence the deletion-contraction recurrence for the chromatic polynomial givesUsing mathematical induction, substitute $p_{C_{s-1}}(x)=(x-1{)}^{s-1}+(-1{)}^{s-1}(x-1)$ to obtainMultiplying by the factor for the attached trees proves the chromatic polynomial of a unicyclic graph formula

Use natural logarithms. A $K_t$ graph minor is represented by $t$ disjoint nonempty branch sets of a graph minor, each inducing a connected graph, with an edge between every pair. The complete graph minor density threshold is defined over nonempty finite graphs byIt uses $e(G)/|G|$, half the average degree of a vertex; the nonempty convention excludes the vacuous density inequality for the empty graph. The PDF has the intended definition with a universal implication over $G$; the TeX transcription corrupts that definition.

Probabilistic lower bound. Put $N=\lfloor t\sqrt{\log t}/4\rfloor$ and take the binomial random graph $G(N,1/2)$. Its edge count has mean $N(N-1)/4$. The Chernoff bound impliesWe show that the probability of a $K_t$ graph minor tends to zero. Ignore connectedness, which only enlarges the set of possible models, and assign each of the $N$ vertices one of $t$ branch labels or an unused label. There are at most $(t+1{)}^N$ assignments.

For any assignment with $t$ nonempty branch sets, at least $t/2$ of them have size at most $2N/t\le \sqrt{\log t}/2$. Between any two such small sets $A,B$, the probability of no edge isThe absence or presence of edges between different pairs of branch sets depends on disjoint sets of random edges, so these events are independent. For this assignment the probability that all small pairs are adjacent is at mostThe union bound over assignments is therefore at mostsince the positive term is $O(t(\log t{)}^{3/2})$ and the negative term has order $t^{7/4}$. There is consequently a graph with no $K_t$ graph minor and with $e(G)/N\ge N/8$. Any constant having the universal forcing property must exceed this ratio. Since $N/8\ge t\sqrt{\log t}/64$ for large $t$,

The auxiliary density lemma contains a typo. Both the original PDF and the TeX print $e(G)\le 11k|G|$ in the hint. This cannot imply its conclusion: for $k\ge 1$, an edgeless graph has only edgeless graph minors, and none satisfies $2\delta (H)\ge |H|+4k-1$. We use the intended dense minor with bounded order and high minimum degree lemma with the hypothesis $e(G)\ge 11k|G|$ for nonempty $G$. The upper-bound argument below depends on that corrected supplied lemma; the literal printed hint is false.

Probabilistic upper bound and the constant seven. Suppose $G$ is nonempty and $e(G)\ge 7t\sqrt{\log t}|G|$, and setThe corrected lemma gives a graph minor $H$ of order $N\le 11k+2$ with $2\delta (H)\ge N+4k-1$. Since $\delta (H)\le N-1$, we also have $N\ge 4k+1$. For large $k$, every vertex has at most $N/3$ nonneighbours, counting itself, becausethe last inequality uses $N\le 11k+2\le 12k-3$. Moreover any two distinct vertices have at leastcommon neighbours.

Choose $2t$ disjoint random $\ell$-sets $A_1,\dots ,A_{2t}$ from $V(H)$, uniformly, which is possible since $2t\ell <4k-1\le N$ for sufficiently large $t$. For a set $A$, let $U(A)$ be the set of vertices having no neighbour in $A$. For each vertex, the probability that all members of a uniformly sampled $\ell$-set are its nonneighbours is at most $3^{-\ell }$, even when sampling without replacement. By linearity of expected value,Call $A$ good if $|U(A)|\le N{3}^{-19\ell /20}$. The Markov inequality shows that a random set is bad with probability at most $3^{-\ell /20}=o(1)$. Thus the expected number of bad sets among our $2t$ samples is $o(t)$.

Conditional on a fixed good $A_i$, the marginal distribution of $A_j$ is uniform among $\ell$-sets outside $A_i$. For there to be no edge between them, all its members must lie in $U(A_i)$. HenceHere $(N/(N-\ell ){)}^{\ell }=\exp (O({\ell }^2/N))=1+o(1)$. Consequently the expected number of nonadjacent pairs of good sets is at mostsince $(19/20)\log 3>1$. Applying the Markov inequality to both counts shows that there exists a choice with fewer than $t$ bad sets and at most $t$ nonadjacent pairs of good sets. Select $t$ of the good sets; they still have at most $t$ missing adjacencies.

Make each selected set connected by fixing one of its vertices as a root and, for each of its other members, adding one unused common neighbour of that member and the root. This uses at most $t(\ell -1)$ additional vertices. Then for each pair with no original edge, choose one vertex in each set and add an unused common neighbour to one of the sets. The added vertex is joined to that set and to the other set, so it preserves connectedness and repairs their adjacency. At most $t$ such repairs are required.

Throughout this process the total number of occupied vertices is at mostSince every pair has at least $4k-1$ common neighbours, an unused choice always exists. The final sets are disjoint connected branch sets of a graph minor with every pair adjacent. They represent $K_t$ in $H$, and hence in $G$, by transitivity of graph minors. This random branch-set construction of a complete graph minor proves

The sharp linear threshold for a four-vertex complete minor. We prove by induction that a graph on $n\ge 4$ vertices with at least $2n-2$ edges has a $K_4$ graph minor. The case $n=4$ is $K_4$ itself. If some edge $uv$ has at most one common neighbour, an edge contraction reduces the order by one and removes exactly $1+|N(u)\cap N(v)|\le 2$ edges. The contracted graph has at least $2(n-1)-2$ edges, so induction applies.

Otherwise every edge is in at least two triangles in a graph. Choose a vertex $v$ incident with an edge. Each vertex $u\in N(v)$ has at least two neighbours of a vertex in $N(v)$, since these are the common neighbours of $u,v$. Thus $G[N(v)]$ has minimum degree of a graph at least two. A longest path in this finite graph has an endpoint adjacent to an earlier nonconsecutive path vertex, and hence contains a cycle in a graph. Together with $v$, this cycle in a graph gives a wheel graph as a subgraph. Divide its rim into three consecutive nonempty connected arcs; these arcs and $\{v\}$ form four pairwise adjacent branch sets of a graph minor. Therefore

With $2n-3$ edges the answer is no. Take the join of graphs of $K_2$ and an independent set of $n-2$ vertices. It has $1+2(n-2)=2n-3$ edges. Among four disjoint putative branch sets of a graph minor, at most two can contain the two vertices of $K_2$. Any connected branch set avoiding them is a singleton in the independent set. At least two such singleton sets would therefore have no edge between them. This excludes a $K_4$ graph minor for every $n\ge 4$ and proves sharpness.

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.^[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.^[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.

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)\le \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.