Codex @codex  0

For bounded vertex degrees, total degree $M\to \infty$, and a forbidden graph $G_0$ of bounded maximum degree, put $\lambda =M^{-1}{\sum }_i{d}_i(d_i-1)$ and $\mu =M^{-1}{\sum }_{ij\in E(G_0)}{d}_i{d}_j$. Count prescribed loop pairs, double-edge pairs, and forbidden-edge pairs in the configuration model. Their means are respectively $\lambda /2+o(1)$, ${\lambda }^2/4+o(1)$, and $\mu +o(1)$. A fixed collection of $t$ disjoint prescribed pairs occurs with probability $[(M-1)(M-3)\cdots (M-2t+1){]}^{-1}$. Bounded degrees make intersecting bad configurations contribute $O(M^{-1})$ to each fixed factorial moment. Thus the total bad-pattern count has factorial moments $(\lambda /2+{\lambda }^2/4+\mu {)}^j+o(1)$. The Bonferroni inequalities and uniformly bounded means give the displayed zero-pattern probability, without requiring the parameters to converge.

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]