The five-cycle and its complement both have no triangle, so $R(3,3)>5$. In a six-vertex graph, any vertex has at least three neighbours or three nonneighbours. In the first triple an edge completes a triangle with the chosen vertex, while no edges give an independent triple. The complementary argument handles three nonneighbours. Hence $R(3,3)=6$.

Now suppose a nine-vertex graph contains no triangle and no independent four-set. Each vertex has at most three neighbours, since its neighbourhood is independent. It cannot have at most two neighbours: its at least six nonneighbours contain, by the result just proved, either a triangle or an independent triple; the former is forbidden and the latter joins the vertex to give an independent four-set. Every degree must therefore equal three. But nine vertices of degree three have odd total degree, contradicting the handshake lemma. Thus $R(3,4)\le 9$.

The Ramsey number $R(s,t)$ is the least $N$ such that every $N$-vertex graph contains a clique of size $s$ or an independent set of size $t$. Take $N=R(s-1,t)+R(s,t-1)$ and choose a vertex $v$. Among its $N-1$ other vertices, either it has at least $R(s-1,t)$ neighbours or it has at least $R(s,t-1)$ nonneighbours.

In the first case those neighbours contain an independent $t$-set or an $(s-1)$-clique, which joins $v$ to form an $s$-clique. In the second case the nonneighbours contain an $s$-clique or an independent $(t-1)$-set, which joins $v$ to form an independent $t$-set. This proves

The chromatic number is the smallest positive integer $q$ for which $p_G(q)>0$. Thus equality of the polynomials implies $\chi (G)=r$, as well as $|V(G)|=n$ and $e(G)=e(T_r(n))$. In particular $G$ contains no $K_{r+1}$, since such a clique requires $r+1$ colors. The equality case in Turán's theorem now gives $\boxed{G\cong T_r(n)}$. This uses more than equality of triangle counts: the polynomial also determines colorability.

The degree of a chromatic polynomial is the number of vertices and the negative of its next coefficient is the number of edges. Equality with $p_{K_n}$ therefore forces $n$ vertices and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges. A simple graph on those vertices with that many edges contains every possible edge, so $\boxed{G\cong K_n}$.

Deletion-contraction also proves the alternating-sign form with nonnegative coefficients. If $G$ has $n$ vertices, $G/e$ has $n-1$, so subtracting its alternating expansion adds its coefficient at each succeeding index:Starting from an edgeless graph gives $a_0=1$ and no constant term when $n>0$.

For the first coefficients, inclusion-exclusion over the forbidden monochromatic edges gives the precise expressionwhere $c(F)$ counts components of the spanning graph $(V(G),F)$, including isolated vertices. Only $F=\varnothing$ gives $x^n$. A rank-one edge set is a single edge, giving coefficient $-m$ at $x^{n-1}$. Rank two comes from every two-edge subset, each with positive sign, and every triangle, each with negative sign. No other simple edge set has rank two: its nontrivial components must be a three-vertex component or two separate edges. ThusThe displayed $a_2$ assertion concerns $n\ge 3$; below this degree the corresponding coefficient is absent and its expression is zero.

For a positive integer $x$, $p_G(x)$ counts proper vertex colorings using a labelled palette of $x$ colors. Choose an edge $e=uv$. Proper colorings of $G-e$ divide into those in which $u,v$ have different colors, counted by $p_G(x)$, and those in which they have the same color, counted by $p_{G/e}(x)$. Thuswhere parallel edges after contraction are suppressed. Induction, using $p_G(x)=x^{|V(G)|}$ for an edgeless graph, produces a polynomial agreeing with every integer coloring count. The polynomial is unique because two polynomials agreeing at infinitely many integers are identical.

The Turán graph $T_r(n)$ is the complete $r$-partite graph whose nonempty part sizes differ by at most one. Write $n=qr+s$, $0\le s<r$: it has $s$ parts of size $q+1$ and $r-s$ parts of size $q$.

Turán's theorem states that every simple $n$-vertex graph with no $K_{r+1}$ has at most $e(T_r(n))$ edges, with equality precisely for a graph isomorphic to $T_r(n)$. Its edge number is half of $n^2$ minus the sum of the squared part sizes.

Add $s$ adjacent to every vertex of $V_1$ and $t$ adjacent to every vertex of $V_2$. Suppose an $s$–$t$ separator $C$ has fewer than $n$ vertices. It cannot contain all of either class. Choose $x\in V_1\setminus C$ and $y\in V_2\setminus C$. No edge can join the remaining two classes, since it would give a three-edge $s$–$t$ path. Hence every neighbour of $x$ lies in $C\cap V_2$, and every neighbour of $y$ lies in $C\cap V_1$. The minimum-degree bound impliesa contradiction. Menger's theorem therefore gives $n$ internally vertex-disjoint $s$–$t$ paths. Each uses at least one vertex of each original class, and only $n$ vertices are available in each class. Every path must consequently use exactly one of each. Their middle edges form a perfect matching.

In the vertex form of Menger's theorem, for distinct nonadjacent vertices $s,t$ of a finite graph, the maximum number of pairwise internally vertex-disjoint $s$–$t$ paths equals the minimum size of an $s$–$t$ vertex separator. A separator is a subset of vertices other than $s,t$ whose deletion leaves no $s$–$t$ path; internally disjoint paths may share their endpoints but no other vertices. Equivalently, between disjoint vertex sets the maximum number of mutually vertex-disjoint connecting paths equals the minimum size of a separating vertex set, where endpoints may be deleted in that set version.

Make a bipartite graph whose two classes index the two partitions, joining $i$ on the left to $j$ on the right exactly when $A_i\cap B_j\ne \varnothing$. For a subset $U$ of left indices, its union of blocks contains $2008|U|$ elements. They all lie in the blocks indexed by $N(U)$, whose union has $2008|N(U)|$ elements. Thus $|N(U)|\ge |U|$. Hall's theorem gives a matching covering all $n$ left vertices, hence also all $n$ right vertices. Its partner map is the required permutation $\pi$.

Hall's theorem states that a finite bipartite graph with classes $L,R$ has a matching covering $L$ if and only if $|N(U)|\ge |U|$ for every $U\subseteq L$. Here $N(U)$ is the set of vertices of $R$ adjacent to at least one member of $U$. Necessity follows because matched partners of $U$ are distinct members of $N(U)$.

For sufficiency induct on $|L|$; zero or one vertex is immediate. If a nonempty proper $U\subset L$ has $|N(U)|=|U|$, Hall's condition holds within the graph on $U,N(U)$. It also holds on the remaining classes: for $T\subseteq L\setminus U$,Induction gives matchings in these two disjoint subgraphs, and their union covers $L$. Otherwise every nonempty proper $U$ has $|N(U)|\ge |U|+1$. Choose any edge $lr$ and delete its two endpoints. Every nonempty subset of the remaining left class was a proper subset of $L$, so deleting $r$ leaves at least as many neighbours as vertices. Induction gives a matching there, and adjoining $lr$ completes the matching. This proves sufficiency in all cases.

For $i=1,\dots ,n-1$, make one block from the edge weights $\{X_{ij}:j>i\}$. These $n-1$ blocks are independent because they contain disjoint edges. Changing one whole block only changes weights of edges incident with vertex $i$. Every matching contains at most one such edge, so its total weight changes by at most one. Comparing an old optimal matching in the new weights and a new optimal matching in the old weights proves that the maximum matching weight also changes by at most one.

Apply the bounded-differences martingale argument to these $n-1$ blocks, givingExposing each edge separately would give a weaker quadratic-in-$n$ denominator. The grouped exposure is what supplies the requested linear denominator. The proof needs only independent weights in $[0,1]$, not identical uniform laws. For $n=1$, the matching weight is deterministically zero; the divided formula is intended for $n\ge 2$.

The general grouping argument is vertex-block concentration of maximum matching weight.

The union area is a bounded measurable function of the centres, with $0\le X\le n\pi$. Fix all centres except one, and let $B$ be the union of the fixed disks. Replacing the remaining disk $D$ changes the area to $|B|+|D\setminus B|$. The second term always lies in $[0,\pi ]$, so the area changes by at most $\pi$, not merely by the weaker bound $2\pi$.

Thus $X/\pi$ has coordinate differences at most one for the $n$ independent centres. The preceding martingale bound givesOne may take $c=1/(2{\pi }^2)$, independently of all centre distributions. Boundedness of the area ensures the conditional expectations exist even when the centre locations have no finite moments.

Azuma's inequality states that if $(M_i{)}_{i=0}^m$ is a martingale with $|M_i-M_{i-1}|\le 1$ almost surely, then for $t\ge 0$,For independent product coordinates $Z_1,\dots ,Z_m$, expose them successively and set $M_i=E[f(Z)\mid Z_1,\dots ,Z_i]$. If changing one coordinate changes $f$ by at most one, the possible conditional means at that exposure have diameter at most one, by averaging the same remaining independent coordinates. Therefore the martingale increments have absolute value at most one. It follows thatFor coordinate bounds $c_i$, the same argument gives denominator $2{\sum }_i{c}_i^2$. The argument extends to arbitrary independent measurable coordinates for an integrable function with these bounds, rather than requiring finite state sets.

On this product, use the Hamming metric $d(x,y)=|\{i:x_i\ne y_i\}|$. The relevant Lipschitz condition is $|f(x)-f(y)|\le d(x,y)$, equivalently changing any one coordinate changes the function by at most one. More generally an $L$-Lipschitz function has bound $Ld(x,y)$. The unit version is the bounded-differences condition used below.

Every vertex in the component can be reached from $v$ by a simple path. The number of potential length-$\ell$ simple paths beginning at $v$ is at most $n^{\ell }$, and each has probability $(1/(2n){)}^{\ell }$ of being present. Counting such paths may count a vertex more than once, so it gives an upper bound on the expected number of reached vertices:Thus $\boxed{K=2}$ works for every $n$. Equivalently the dominating branching process has mean offspring one half and expected total progeny two.

Explore the component of one vertex by processing discovered vertices in order. At each step, the number of newly discovered neighbours is a binomial variable with at most $n$ trials and success probability $1/(2n)$, on previously unexposed independent edges. Pad each step with independent dummy trials. This couples the exploration below independent offspring variables ${\xi }_i\sim \mathrm{Bin}(n,1/(2n))$, each of mean one half.

If the component has at least $k\ge 2$ vertices, after $k-1$ vertices have been processed at least $k-1$ offspring must have been found. HenceThe sum is binomial with mean $\mu =(k-1)/2$. The multiplicative Chernoff inequality $P(B\ge 2\mu )\le (e/4{)}^{\mu }$ therefore givesA union bound over all vertices bounds the probability of any component of size at least $k$ by $n{e}^{-c(k-1)}$. Taking $k=\lceil \alpha {\log }_{e}n\rceil$ with any $\alpha >1/c$, for example ten, makes this tend to zero. Thus the largest component is at most a constant times $\log n$ with high probability.

Realize the random graph process by giving every edge an independent uniform arrival time. For a fixed four-set $S$, only its six internal edges and its $4(n-4)$ outgoing edges affect whether it is an isolated clique. It is an isolated clique at some time exactly when all six internal edges arrive before every outgoing edge.

The relative ordering of these $4n-10$ edges is uniform. The chance that the first six are exactly the six internal edges is ${\left(\genfrac{}{}{0ex}{}{4n-10}{6}\right)}^{-1}$. A union bound over the possible vertex sets givesEdges entirely outside $S$ are irrelevant. Counting the whole arrival-order event avoids an invalid union over continuously many times.

This is an example of isolated clique appearance in a uniform random graph process.

Let $X$ count the four-vertex sets spanning a clique. Its expectation is $\mu =\left(\genfrac{}{}{0ex}{}{n}{4}\right)p^6$. If $p\ll n^{-2/3}$, then $\mu \to 0$ and Markov's inequality gives $P(X>0)\to 0$.

Now suppose $p\gg n^{-2/3}$. Then $\mu \to \infty$. Two distinct clique indicators are independent unless their vertex sets share at least two vertices. An overlap of two vertices gives $O(n^6)$ ordered pairs requiring eleven distinct edges; an overlap of three gives $O(n^5)$ pairs requiring nine edges. ConsequentlyThe preceding second-moment bound therefore gives $P(X=0)\to 0$. Thusis a threshold for the appearance of a four-clique. Sharing just one vertex creates no dependence because the two edge sets are disjoint.

Assume $EX>0$, as required by the denominators. Since each indicator has variance at most its expectation, and independent event pairs have zero covariance,The sum uses ordered pairs, matching the covariance expansion. Chebyshev's inequality now givesIf $EX=0$, $X=0$ almost surely and the divided expression is not the useful form of the bound.