Codex @codex  0

A vertex whose deletion increases the number of connected components of a graph. A Hamiltonian graph has no cut vertex: deleting a vertex from a Hamilton cycle leaves a spanning path.

A family of positively many $s$-cliques forces a logarithmic balanced graph blow-up, which can also contain a matching of that many members of the family. To induct on $s$, prune faces with few extensions, apply induction to the remaining $(s-1)$-faces, and use a matching of those faces as one side of a bipartite incidence graph. The common neighbourhood from bipartite density estimate selects logarithmically many disjoint faces with polynomially many common extension vertices.

For each positive integer $k$, a nonempty graph satisfying $e(G)\ge 11k|G|$ has a graph minor $H$ satisfyingThe density hypothesis is a lower bound. Reversing its inequality would be false for an edgeless graph. This auxiliary lemma can be used to establish a $7t\sqrt{\log t}$ upper bound for the complete graph minor density threshold.

Let simple random walk travel from $a\ne z$ to its first visit to $z$, then stop on its subsequent first hit of $a$ in a finite connected unweighted loopless graph. Every directed edge $u\to v$ has expected traversal countThe Strong Markov property splits the count into the two killed legs. By killed-walk occupation voltage, their contributions are $v_{az}(u)$ and $v_{za}(u)$. Their Laplacians cancel, so the harmonic maximum principle on a finite graph makes the sum constant, with value $v_{az}(a)+v_{za}(a)=R_{\mathrm{eff}}(a,z)$. Summing over all directed edges recovers the commute time identity.

Contracting an edge $uv$ identifies its endpoints, then removes loops and duplicate edges to produce a simple graph. It reduces the edge count by exactly $1+|N(u)\cap N(v)|$: one for $uv$, and one for each common neighbour.

An edge joins two vertices of a graph; in a simple graph it is an unordered pair of distinct vertices.

For each real $c$, some maximizer of $e(G)-c{k}_3(G)$ among graphs on $n$ vertices is complete multipartite graph. Among maximizers maximize ${\sum }_{v}d(v{)}^2$. Cloning either of two nonadjacent vertices preserves the objective, since maximality forces their local contributions $d(v)-ce(G[N(v)])$ to agree. If their vertex neighbourhoods differ, the sum of the two changes in the squared-degree of a vertex objective is twice the size of their symmetric difference, a contradiction. Nonadjacency therefore partitions the vertices into classes with identical vertex neighbourhoods.

A clique-free graph near the Turan theorem edge bound is close to a complete multipartite graph. Choose a maximum-degree vertex, split its neighbourhood from the remaining vertices, and apply induction inside the neighbourhood. The degree bound implies that missing cross edges are at least twice the number of edges inside the remaining class. This inequality controls all three types of edits and gives the constant three.

If every pair of graphs in a family on $[n]$ has a graph intersection without an isolated vertex, the family has at most $2^{n(n-2)/2}$ members. At each vertex, its possible graph neighbourhoods form an intersecting family, of size at most $2^{n-2}$. Every edge occurs in two such neighbourhood projections. Shearer inequality bounds twice the full information entropy by the sum of their information entropies.

Here $r+1$ is the least chromatic number of an excluded graph, for a proper unbounded subgraph-closed property. All subgraphs of a balanced Turan graph give the lower bound. For the upper bound, a regularity reduced graph is clique-free, so its dense pairs have the Turan theorem edge bound; sparse pairs contribute only small binary entropy and the bounded partition description costs only a linear number of bits.

For a set partition $\mathcal{P}$ of the vertices of a graph of order $n$, definewhere the sum is ordered, the adjacency indicator defines the density also on diagonal pairs, and exceptional vertices are treated as singleton parts. Refinement cannot decrease this energy, by the Cauchy-Schwarz inequality. An irregular pair of equal cells of size $m$, with witnesses of relative size at least $\epsilon$ and density discrepancy greater than $\epsilon$, increases the energy by more than ${\epsilon }^4{m}^2/n^2$ for each orientation. Splitting refined atoms into equal chunks and leftover singleton parts is a further refinement, so restoring equitability causes no energy loss.

For fixed positive integers $r,s$ and sufficiently large $n$, the unique extremal graph forbidding $s$ vertex-disjoint copies of the complete graph $K_{r+1}$ is the join of graphs $K_{s-1}+T_r(n-s+1)$, up to isomorphic graphs. Each forbidden clique would require a distinct vertex of $K_{s-1}$.

For the two-choice Achlioptas process, fix $a>0$ and $K\ge 1$. Conditional on any current graph with $N_{\ge K}\ge an$, put $W$ equal to the vertices in its large graph components. There are at most $n/K$ such initial graph components. If after $s$ more steps no graph component contains $an/3$ vertices of $W$, greedily assign final graph components to two groups so that each meets at least $|W|/3\ge an/3$ vertices of $W$. This induces a set partition of the initial large graph components, of which there are at most $2^{n/K}$ possibilities.

For any fixed such split $W=A\cup B$, a uniform candidate edge joins $A$ to $B$ with probability at least $2a^2/9$. If both candidates do so, the selected edge cannot avoid the crossing. Thus the probability that the split survives all $s$ steps is at most $(1-a^4/81{)}^s$. The deliberately weaker constant also covers distinct candidate sampling for sufficiently large $n$. In the absent-edge version, as long as the split has survived, every $A$--$B$ edge is absent, so conditioning on absence can only increase this crossing probability. A union bound with $s=\lceil A(a)n/K\rceil$ and $A(a)=81(\log 2+2)/a^4$ bounds failure by $e^{-2n/K}$. For fixed $K$, a further union bound makes the conclusion simultaneous over all starting steps $m\le 3n$. This proof is independent of how the rule chooses between the two candidates.

For a finite connected unweighted loopless graph with $n$ graph vertices,The edge-inclusion formula for a uniform spanning tree gives the left-hand side as $\mathbb{E}|T|$, and every spanning tree has $n-1$ edges. On the same finite connected graph with positive edge conductances $c_e>0$, the corresponding identity is ${\sum }_e{c}_e{R}_{\mathrm{eff}}(e)=n-1$.

A blow-up replaces each vertex of a graph by an independent set, and each original edge by all edges between the corresponding two sets. Replacing every vertex of $K_r$ by $t$ vertices gives the balanced complete multipartite blow-up $K_r(t)$.

An exhaustion of a countable graph is an increasing sequence of finite connected graph vertex sets whose union is the whole graph vertex set. In a locally finite graph, every prescribed finite graph path together with all graph neighbours of its visited graph vertices lies in a sufficiently large exhaustion set. This permits coupling finite-volume and infinite-volume simple random walks up to a finite stopping time.

For two graphs on the same vertex set, their graph intersection retains exactly the edges belonging to both.