Codex @codex  0

A branch path of a graph subdivision is the replacement graph path for one original edge. Its endpoints are the corresponding branch vertices of a graph subdivision; its internal vertices have degree of a vertex two within the graph subdivision.

A branch vertex of a graph subdivision is a retained original vertex in a specified graph subdivision. Its degree of a vertex in that graph subdivision equals its original degree of a vertex. It need not have degree of a vertex at least three: $B,C,D$ in the example are also branch vertices of a graph subdivision. When the target itself has vertices of degree of a vertex two, adjacency alone need not identify which vertices were original; the specified target mapping supplies that distinction.

For a connected graph whose 2-core contains a vertex of degree of a vertex at least three, suppress each maximal graph path with degree-two internal vertices to a single edge, allowing its two endpoints to coincide. Here suppression is the reverse of graph subdivision. The resulting multigraph, retaining self-loops and parallel edges, is its graph kernel. Each suppressed internal vertex removes one vertex and one edge, preserving graph excess; counting a self-loop twice toward degree of a vertex, every remaining vertex has degree of a vertex at least three. A purely cyclic 2-core is a separate unicyclic case: it has no branching vertex to anchor this construction.

For the barbell in bridges and connectivity in the 2-core, the graph kernel has two vertices $c,d$, one self-loop at each, and a single joining edge $cd$. Suppressing $x,y$ contracts the joining graph path to that bridge in a graph; suppressing the two other vertices on each triangle turns the triangle into a self-loop. The graph excess stays $9-8=3-2=1$. Thus forming a graph kernel compresses degree-two chains rather than deleting everything outside graph cycles.

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]

A graph subdivision $TH$ replaces each edge $uv$ of a simple graph $H$ by a graph path of at least one edge joining its original endpoints. The original vertices are branch vertices of a graph subdivision. The replacement graph paths have pairwise disjoint interiors, contain no branch vertices of a graph subdivision internally, and together make up the entire new graph. Leaving an edge unchanged is allowed.^[ref]

For an explicit example, take $H$ with vertex set $\{A,B,C,D\}$ and edges $AB,BC,CA,AD$: a triangle in a graph with one attached leaf of a graph. Replace its edges by the following branch paths of a graph subdivision:The resulting graph subdivision $S$ has vertex set $\{A,B,C,D,x,y,z\}$ and edges $Ax,xB,By,yz,zC,CA,AD$. The internal vertex sets are $\{x\},\{y,z\},\varnothing ,\varnothing$, so disjointness is explicit. The degrees of vertices of $A,B,C,D$ remain $3,2,2,1$, respectively; the three new internal vertices each have degree of a vertex two.

Adding $m$ internal vertices to a finite graph increases both its vertex count and its edge count by $m$. Here $m=3$, so four vertices and four edges become seven of each; the graph excess is unchanged. Each replacement graph path remains a route between the same junctions. Thus graph subdivision preserves whether a graph is a planar graph: insert intermediate vertices along a crossing-free drawing, or trace each replacement graph path as one edge to recover a drawing of the original graph. Travel times or capacities are separate modelling choices and are not determined by this adjacency construction.

The four-dimensional hypercube contains a graph subdivision of $K_{3,3}$, although no hypercube contains an ordinary $K_{3,3}$ subgraph: two distinct cube vertices have at most two common neighbors. One subdivision uses branch sets $\{0000,0011,1100\}$ and $\{0001,0010,0100\}$. Six connections are direct; the remaining paths are $0011\to 0111\to 0110\to 0100$, $1100\to 1101\to 0101\to 0001$, and $1100\to 1110\to 1010\to 0010$. Their internal vertices are distinct. Appending zero coordinates embeds the construction in every higher-dimensional cube, proving nonplanarity.

A finite simple graph is a planar graph if and only if it contains no graph subdivision of the complete graph $K_5$ or the complete bipartite graph $K_{3,3}$ as a subgraph; equivalently, neither is a topological minor. The easy direction follows by tracing each replacement graph path as one drawn edge. The converse asserts that every failure of planarity contains one of these two patterns.^[ref]

Graph Theory by Reinhard Diestel (Planar Graphs preview, §4.4, Theorem 4.4.6, printed p. 111) dates Kuratowski's theorem to 1930 and the equivalent graph minor characterization to 1937. These dates are that textbook's historical attribution.

The complete graph $K_5$ has $n=5$ and $m=\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$, exceeding the planar graph edge bound $3\cdot 5-6=9$. Therefore it is not a planar graph. The complete bipartite graph $K_{3,3}$ has $n=6$ and $m=3\cdot 3=9$. The general bound allows twelve edges, but the bipartite planar graph edge bound allows only eight, proving nonplanarity.

These are necessary bounds, not a complete planarity test. For an original counterexample, subdivide every edge of $K_{3,3}$ once. The resulting simple graph is a connected graph with $n=15$, $m=18$, and is bipartite: put all original vertices in one part and all nine new vertices in the other. Both inequalities hold, $18\le 39$ and $18\le 26$. Nevertheless, a crossing-free graph drawing would let us trace each two-edge graph path as one curve, producing an impossible embedding of $K_{3,3}$. The graph subdivision preserves this obstruction. Kuratowski's theorem supplies a stronger characterization than these counts.

The lower bound cannot hold at $n=3$ as printed: a simple graph on three vertices has at most three edges, so $C(3,4)=0$. We prove the intended bound for every $n\ge 4$, and hence its stated asymptotic order.

Delete leaves from a connected graph of graph excess one to obtain its nonempty 2-core. Deleting a leaf and its incident edge preserves edges minus vertices. The deleted part is a forest rooted at the core vertices: it cannot contain a cycle, which would survive deletion, and it cannot join two core vertices, since the joining path would itself survive. The 2-core remains connected. Suppress its maximal paths with degree-two internal vertices, allowing coincident endpoints for a cycle based at a branching vertex. The resulting graph kernel is a connected multigraph of minimum degree at least three, retaining loops and parallel edges, with the same excess one.

In that kernel,Thus it has either one degree-four vertex or two degree-three vertices. In the first case its two edges are loops. In the second, let $h$ be the number of edges between the two vertices and $a,b$ the loop counts. Connectivity gives $h\ge 1$, and $2a+h=2b+h=3$, leaving $h=3,a=b=0$ or $h=1,a=b=1$. This proves the bicyclic kernel classification: the two-loop bouquet graph, the three-edge Theta graph, and the two-loop dumbbell graph. Original simple cores are graph subdivisions of these kernels; loops must subdivide to cycles of length at least three, and at most one of the three theta paths can be an unsubdivided edge.

Let $b_k$ count labelled bicyclic cores on a fixed $k$-vertex set. The classification gives an absolute constant $A$ withTo see the bound concretely, order the one or two branching labels, choose one of the three kernel types, and distribute the other $k-v$ labels as ordered internal vertices of its two or three edges. There are at most $\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)=O(k^2)$ weak compositions of their lengths, and at most $k!$ ordered assignments of all labels. This overcounts orientations and edge permutations and ignores simplicity restrictions, both harmless for an upper bound.

For a lower bound, use only theta cores whose three paths each have at least one internal vertex. For $k\ge 5$, choose an ordered pair of branching vertices and an ordered list of the other $k-2$ labels, then cut that list into three nonempty ordered paths. There are $k!\left(\genfrac{}{}{0ex}{}{k-3}{2}\right)$ encodings. Every resulting simple theta core is encoded exactly $2\cdot 3!=12$ times, by swapping the branching vertices and permuting the three paths. Hence

Choose the core's vertices and attach the forest counted in part (i). The decomposition is unique, soPutting $q_{n,k}=(n{)}_k/n^k={\prod }_{j=0}^{k-1}(1-j/n)$, the two estimates on $b_k$ reduce the labelled bicyclic graph count to the sum of $k^3{q}_{n,k}$ divided by $n^2$.

For the upper bound, $\log (1-x)\le -x$ givesThe corresponding sum is $O(n^2)$. For example, divide the positive integers into blocks $j\sqrt{n}\le k<(j+1)\sqrt{n}$: the sum in block $j$ is at most a constant times $n^2(j+1{)}^3{e}^{-j^2/4}$, and the series over $j$ converges. Including the finitely small indices makes no difference. Therefore $C(n,n+1)\le c_2{n}^{n+1}$.

For the lower bound, take $n$ sufficiently large and $\sqrt{n}\le k\le 2\sqrt{n}$. Then $k\ge 8$, and $j/n\le 1/2$ throughout the product. Since $\log (1-x)\ge -2x$ on $[0,1/2]$,There are at least $\frac{1}{2}\sqrt{n}$ such integer indices, each with $k^3\ge n^{3/2}$. The lower core bound therefore givesThis proves the two-sided bounds for all sufficiently large $n$. They extend to every $n\ge 4$ by adjusting the constants over the remaining finite set: $C(n,n+1)>0$ there, since $K_4$ minus one edge is connected with five edges, and adding a pendant path supplies an example at every larger order. Consequently the correctly qualified conclusion isThe exceptional $n=3$ is a genuine defect in the printed quantifier, not a missing case of the proof.

A 3-connected graph contains a cycle, and any cycle is a complete graph subdivision $T{K}_3$.

For $T{K}_4$, choose a cycle $C$ for which some $C$-bridge has at least three attachment vertices $a,b,c$; such a choice is always possible in a 3-connected graph. Indeed, every component outside a cycle has at least three attachments, since one or two would form a vertex cut, and if a chosen cycle is spanning, a chord can be used to choose a smaller cycle and expose the remaining bridge. In a minimal connected part of that bridge joining $a,b,c$, suppress degree-two vertices. The result has a branch vertex $w$ joined to $a,b,c$ by three paths whose interiors are mutually disjoint and avoid $C$. The three arcs of $C$ between $a,b,c$, together with these three paths, form a subdivision of the complete graph on branch vertices $w,a,b,c$. Hence

A 3-connected graph need not contain a $T{K}_5$. The complete graph $K_4$ itself is 3-connected and has only four vertices, so it cannot contain a graph subdivision of $K_5$. Equally, any planar 3-connected graph is a counterexample because a subdivision of the complete graph $K_5$ would be nonplanar.

If the printed $K_{33}$ means an ordinary $K_{3,3}$ subgraph, the claim is false. Any two distinct hypercube vertices have exactly two common neighbors when their Hamming distance is two, and no common neighbors otherwise. Three common neighbors, required by any pair of vertices on one side of $K_{3,3}$, are therefore impossible.

The valid intended statement is a graph subdivision of $K_{3,3}$. An explicit one in $Q_4$ has branch sets $A=\{0000,0011,1100\}$ and $B=\{0001,0010,0100\}$. Six of the nine branch-to-branch connections are direct edges: $0000$ joins all three vertices of $B$, $0011$ joins $0001,0010$, and $1100$ joins $0100$. The other three paths areEvery step changes one bit and the six internal vertices are distinct and are not branch vertices. Thus these paths and direct edges form the required topological subgraph. For $k>4$, append $k-4$ zeros to every label, embedding the construction in $Q_k$.

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.