Codex @codex  0

The Sidorenko conjecture states that every bipartite graph $H$ satisfiesfor every bipartite host graph $G$. Thus a random map is at least as likely to preserve every edge as the heuristic that treats the edge constraints independently predicts.

A substructure $M\subseteq N$ is simply closed when each existential quantifier-free formula over $M$ realized in $N$ is already realized in $M$. A single quantified variable suffices in the definition; iterating covers finite tuples. This property is also called existential closure in this specified extension. It is weaker than being an elementary substructure.

An undirected simple graph is exactly a pair of setsThus every edge is a two-element set of distinct vertices. The unordered pair $\{u,v\}$ equals $\{v,u\}$, so there is no direction. The distinctness condition excludes self-loops, and using a set of edges excludes parallel copies. A simple graph may have vertices with no incident edges; $E$ does not by itself determine $V$. For example, $(\{A,B\},\{AB\})$ and $(\{A,B,C\},\{AB\})$ have the same edge set but different vertex sets.^[ref]

In the six-vertex example, the vertex neighbourhood of $C$ is $\Gamma (C)=\{A,B,D\}$, so its degree of a vertex is $\mathrm{deg}(C)=3$. In label order $A,B,C,D,E,F$, the degree sequence isThis is the handshaking lemma: count each edge once at each of its two endpoints. The average degree of a graph here is $14/6=7/3$. The degree sequence is a compact consistency check on an edge list; an odd sum could not describe any finite undirected graph. It also forces the number of odd degrees of vertices to be even, since the even terms do not affect the parity of the sum.

The adjacency matrix in the figure uses label order $A,B,C,D,E,F$. Its entry $M_{uv}$ is one exactly when $\{u,v\}\in E$, and zero otherwise. It is a symmetric matrix with zero diagonal, and each row sum gives the corresponding vertex degree. For example, row $C$ is $(1,1,0,1,0,0)$. The fourteen ones count both directions of the seven undirected edges; they do not indicate fourteen different edges. This translates a picture into a representation suitable for calculation.

The restrictions matter. A directed graph uses an ordered pair to distinguish $u\to v$ from $v\to u$, so reachability can depend on direction. A multigraph can contain several distinct edges between the same vertices; adding another $CD$ would raise $\mathrm{deg}(C)$ and $\mathrm{deg}(D)$ to four without adding a new neighbour. A self-loop at $A$ contributes two to its undirected vertex degree, making it four, because both endpoints lie at $A$. Specify whether self-loops are allowed in a multigraph. Finally, a weighted graph attaches numerical information to edges: if links carry travel times, minimizing the number of edges need not minimize total time. These are changes to the model, rather than changes to how the same simple graph is drawn.

A finite simple graph that is a cubic graph and has a perfect matching admits a partition of a set of its edges into graph paths of length three.

Proof. Delete a perfect matching $M$. The remaining spanning subgraph has vertex degree two at every vertex, so it consists of disjoint graph cycles. Orient each cyclically, giving a successor bijection $s$. Replace each $uv\in M$ by the graph path $s(u),u,v,s(v)$. The four vertices are distinct: the successor edges are not in $M$, neither is a self-loop, and injectivity of $s$ excludes $s(u)=s(v)$. Every edge of $M$ appears once in the middle, and every other edge appears once at its unique tail. Thus the graph paths cover every edge exactly once. In particular, the perfect matching theorem for a cubic graph with at most two bridges guarantees this decomposition under its hypotheses.

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.

A tree is a nonempty connected graph containing no graph cycle. Think of seven locations joined so that everyone can reach everyone else, but no connection supplies an alternative route. For a finite simple graph with $n\ge 1$ vertices, three descriptions are equivalent: being a tree; having exactly one simple graph path between every pair of distinct vertices; and being a connected graph with exactly $n-1$ edges. Here a simple graph path repeats no vertex. Connectedness in the last description is essential. ^[ref]

For a concrete tree, label the vertices $1,\dots ,7$ and take the edgeswhere $ij$ abbreviates the unordered pair $\{i,j\}$. There are seven vertices and six edges. The unique graph path from $4$ to $7$ is $4,2,1,3,6,7$, using five edges. The degree sequence in label order is $(2,3,2,1,1,2,1)$: its sum is $12=2\cdot 6$, as the degree-sum formula predicts. Each of $4,5,7$ is a leaf of a graph, having vertex degree one.

Deleting edge $13$ leaves precisely two connected components of a graph, on $\{1,2,4,5\}$ and $\{3,6,7\}$. Every edge of a tree is a bridge in a graph. Instead add edge $57$ to the original tree: it closes the unique existing graph path $5,2,1,3,6,7$ into exactly one graph cycle. Thus a tree provides economical connections with no redundancy: a single failed link separates locations. Every finite tree with at least two vertices has at least two instances of a leaf of a graph; the endpoints of a longest graph path supply them. ^[ref]

The number $n-1$ alone proves nothing about connectedness: a cycle graph on $1,\dots ,6$ together with an isolated vertex $7$ has seven vertices and six edges, yet is disconnected. Briefly, two different simple graph paths between the same vertices would contain a graph cycle. Repeatedly removing a leaf of a graph and its incident edge proves the tree count $n-1$ by mathematical induction, starting with one vertex and no edges.

How many edges can we retain while excluding a prescribed clique? For integers $r\ge 1$ and $n\ge 0$, every simple graph on $n$ vertices containing no complete subgraph $K_{r+1}$ satisfiesEquality holds exactly for the Turán graph $T_r(n)$, up to graph isomorphism. Thus the extremal number is $\mathrm{ex}(n,K_{r+1})=t_r(n)$.^[ref]

For example, $T_3(8)$ has independent sets of sizes $3,3,2$ and $21$ edges, as counted in Turán graph. It contains triangles in a graph, but no four-vertex clique. Consequently any simple graph on eight vertices with $22$ edges contains $K_4$, while $21$ edges alone do not force one. Excluding larger cliques permits denser graphs; Mantel theorem is precisely the first nontrivial case.

A short proof outline uses Zykov symmetrization. If an extremizer is not a complete multipartite graph, it has vertices $x,y,z$ with $xy,xz$ absent and $yz$ present. If either $y$ or $z$ has larger vertex degree than $x$, clone that vertex in place of $x$. Otherwise replace both $y,z$ by nonadjacent clones of $x$, gaining $2d(x)-d(y)-d(z)+1>0$ edges. Both contradict extremality; balancing the resulting at most $r$ parts gives $T_r(n)$.^[ref]

The vertex cloning in a graph step preserves clique exclusion because any clique using a clone can substitute its original vertex; nonadjacent clones cannot occur together in a clique. At most $r$ parts can be nonempty, since selecting one vertex from each gives a clique. If fewer than $r$ parts are nonempty and one has at least two vertices, splitting it creates more edges, so it cannot be extremal. For $r=1$ the bound is zero. For $r\ge n$, the Turán graph is $K_n$, and the bound is the total $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges.

A vertex cover chooses vertices that collectively touch every edge of a graph. Think of placing monitors at junctions: if a monitor watches every connection incident to its junction, a vertex cover watches all connections. The minimum vertex cover asks how few monitors suffice. This is a model of covering connections through their endpoints, rather than of monitoring distances in the drawing.

For a finite simple graph $G=(V,E)$, a vertex cover is a subset $C\subseteq V$ satisfyingBoth endpoints may be selected; the condition requires at least one. An isolated vertex covers no edge, so a minimum vertex cover never needs it.^[ref]

Take the cycle graph $C_5$ with vertices $0,1,2,3,4$ and edges $01,12,23,34,40$. The set $C=\{1,3,4\}$ is a vertex cover: vertex $1$ covers $01$ and $12$, vertex $3$ covers $23$ and $34$, and vertex $4$ covers $40$ as well as $34$. In particular, the closing edge $40$ is covered even though vertex $0$ is unselected.

The unselected vertices $I=V\setminus C=\{0,2\}$ form an independent set. This is the key connection: an edge missed by $C$ would have both endpoints in $I$, precisely what an independent set forbids. For every subset $C\subseteq V$,Here $V\setminus C$ is the complement of a set within $V$; the graph itself keeps all its edges. The complement graph is a different construction.^[ref]

The endpoints of any maximal matching form a vertex cover: an edge avoiding all endpoints would enlarge that matching in a graph. Consequently a graph with no matching in a graph of size $s$ has a vertex cover of size at most $2(s-1)$. This supplies a convenient vertex cover, but it need not be a minimum vertex cover.

The vertex cover decision problem asks whether a finite simple graph $G$ has a vertex cover containing at most $k$ vertices. For an uncovered edge $uv$, any valid vertex cover contains $u$ or $v$. Branch on these two possibilities, delete the chosen vertex and its incident edges, and decrease $k$ by one. An edgeless graph accepts and a nonempty graph with $k=0$ rejects. The search tree has at most $2^k$ leaves, giving running time $O(2^k(|V|+|E|))$ with straightforward copying. Thus this parameterization is fixed-parameter tractable.

A walk records a journey through a graph as a finite alternating sequencewhere each edge $e_i$ joins the consecutive vertices $v_{i-1}$ and $v_i$. Both vertices and edges may repeat. Its length is $m$, counting edge traversals with repetitions, rather than counting different edges or measuring the drawing. Here a graph path means a walk with no repeated vertices; a trail instead forbids repeated edges. These conventions distinguish a journey's record from the subgraph consisting of the connections it used.^[ref]

Unless stated otherwise, the examples below use a finite simple graph that is an undirected graph, so an edge may be traversed in either direction. In a multigraph, retain each edge's individual identity as well as its endpoint vertices: two parallel edges are different choices for the same step. If self-loops are allowed, traversing one leaves the current vertex unchanged but adds one to the length. In a directed graph, each step must follow its directed edge from its initial to its terminal vertex, giving a directed walk; reversing a journey need not be possible.^[ref]

We allow the zero-length walk $(v)$ at every vertex $v$. It uses no edges, so it is also a trail and a graph path, and its coinciding endpoints make it a closed walk. This means staying put is a legitimate journey; a graph with no vertices has no such walk. Positive-length restrictions will be stated explicitly.^[ref]

Use the same constructed graph throughout these three sections:Here $AB$ denotes the unordered pair $\{A,B\}$, and $CA=AC$. Two triangles in a graph, $ABC$ and $ADE$, share $A$, with one extra edge $AF$. These are schematic connections, not measured roads; the highlighted connections in the diagram show which edges are used, while the numbered sequence records their order.

The length-six walk $B,C,A,B,C,A,F$ uses $BC$ and $CA$ twice, so it is not a trail. The length-six trail $B,C,A,D,E,A,F$ returns to $A$ but uses six different edges, so it is not a graph path. The length-three graph path $B,C,A,F$ repeats neither vertices nor edges. Thusfor this particular graph. The restrictions answer different routing questions: revisiting a junction is harmless for many journeys, whereas reusing a serviced road segment can matter for an inspection route. Travel costs require a weighted graph; a walk's cost adds the weight of each traversal, even when an edge is used again.

Every finite walk from $s$ to $t$ contains a graph path from $s$ to $t$ after deleting detours. For a proof outline, if $v_i=v_j$ with $i<j$, delete the intervening closed walk. The retained steps still meet at the same vertex, and the length strictly decreases. Repeating terminates with no repeated vertices, or with the zero-length graph path when $s=t$. This explains why reachability can be formulated using either walks or graph paths. With nonnegative edge weights, deletion also cannot increase cost, connecting the argument to the shortest path problem; with negative weights that cost conclusion fails.^[ref]