A threshold function $p^{\ast }(n)$ has the following meaning: if $p/p^{\ast }\to 0$, the probability of a $K_5$ tends to zero; if $p/p^{\ast }\to \infty$, that probability tends to one. Behavior at a fixed constant multiple is not specified by this definition.

Let $X$ count the five-vertex subsets spanning $K_5$ in the Erdős-Rényi model $G(n,p)$. ThenIf $p\ll n^{-1/2}$, then $\mu \to 0$, so Markov inequality gives $P(X>0)\le \mu \to 0$.

Now let $p=n^{-1/2}w$ with $w\to \infty$. Then $\mu \sim w^{10}/120\to \infty$. Distinct copies have dependent indicators only if their vertex sets share at least two vertices. If they share $j\in \{2,3,4\}$ vertices, they share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges; there are $O(n^{10-j})$ ordered such pairs, and their joint probability is $p^{20-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. ConsequentlyPart (b) gives $P(X=0)\to 0$. ThereforeThis is the five-vertex instance of the fixed-size clique appearance threshold.

For an indicator $I_i$, $\mathrm{Var}(I_i)=P(A_i)(1-P(A_i))\le P(A_i)$. Covariances vanish for independent pairs. For dependent distinct pairs,Expanding the variance, with ordered pairs as in the definition of $\Delta$, givesFor sufficiently large $n$, ${\mu }_n>0$. By Chebyshev inequality,This is the second moment method: a vanishing relative variance makes a zero count unlikely.

For a nonnegative random variable $Y$ and $a>0$, Markov inequality statesFor a random variable $X$ of finite mean $\mu$ and variance ${\sigma }^2$, Chebyshev inequality states that for every $t>0$,To prove it, apply Markov inequality to the nonnegative variable $(X-\mu {)}^2$ at threshold $t^2$:

Verify Hall's marriage theorem. Let $S\subseteq X$; the empty case is immediate. If $0<|S|\le ϵn$, any $x\in S$ has at least $ϵn$ neighbors in $Y$, so $|N(S)|\ge |S|$.

Next suppose $ϵn<|S|\le (1-ϵ)n$. If $|N(S)|<|S|$, then $T=Y\setminus N(S)$ has $|T|>n-|S|\ge ϵn$. There are no edges between $S$ and $T$, so $d(S,T)=0$. But the regularity assumption impliesa contradiction.

Finally, if $|S|>(1-ϵ)n$, then $|X\setminus S|<ϵn$. Every $y\in Y$ has at least $ϵn$ neighbors in $X$, so at least one of them lies in $S$. Thus $N(S)=Y$ and $|N(S)|=n\ge |S|$.

All possible sizes of $S$ are covered, even if the middle range is empty. Hall's condition holds, so there is a perfect matching between $X$ and $Y$. This is the perfect matching criterion for a regular pair with minimum degree.

For disjoint nonempty vertex sets $X,Y$, let $e(X,Y)$ count edges with one endpoint in each. Their density isFor $0<ϵ<1$, the pair is a regular pair of vertex sets if all $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge ϵ|X|$ and $|Y^{\prime }|\ge ϵ|Y|$ satisfyUsing the convention with a strict bound less than $ϵ$ instead gives the same argument below; the assumed density is strictly larger than $ϵ$.

Hall's marriage theorem states that a finite bipartite graph with vertex classes $X,Y$ has a matching covering $X$ if and only ifNecessity follows because the matched neighbors of the vertices in $S$ are distinct members of $N(S)$.

For sufficiency, induct on $|X|$. The empty case is immediate. First suppose there is a nonempty proper subset $S\subset X$ with $|N(S)|=|S|$. The induced graph between $S$ and $N(S)$ satisfies Hall's condition, so induction matches $S$. In the remaining graph between $X\setminus S$ and $Y\setminus N(S)$, every $T\subseteq X\setminus S$ satisfiesInduction matches the rest, and the two matchings are disjoint.

Otherwise every nonempty proper $S\subset X$ has $|N(S)|\ge |S|+1$. Choose any edge $xy$, which exists by Hall's condition if $X$ is nonempty. Delete $x$ and $y$. Every nonempty subset of $X\setminus \{x\}$ loses at most one neighbor and therefore still satisfies Hall's condition. Induction provides a matching of this smaller graph; append $xy$. If $|X|=1$, choosing its neighbor already completes the argument. This proves the theorem.

No. Colour the positive integers by alternating dyadic blocks:Every positive integer $x$ and its double $2x$ have opposite colours. A nonempty set closed under addition contains both $x$ and $x+x=2x$, so no such set can lie in one class. In particular there is no infinite monochromatic additive subsemigroup.

The suggested arithmetic-progression argument gives another way to see the obstruction. If $a\in S$ and $S$ is closed under addition, then $a,2a,3a,\dots$ all lie in $S$. But every infinite arithmetic progression of positive step $d$ meets every sufficiently long dyadic block, because a block of at least $d$ consecutive integers contains a representative of the progression's residue class. Both colours contain arbitrarily long blocks, so neither colour contains an infinite arithmetic progression.

Colour the edge $ij$ of the complete graph on $\{1,\dots ,6\}$ by the class containing $|j-i|$. Part (a) gives $R(3,3)\le 6$, so there is a monochromatic triangle with vertices $i<j<k$. Its three edge differences areThey are positive integers in one class. Hence every two-colouring of the positive integers has a monochromatic solution of $x+y=z$. This is the two-colour Schur theorem. The two summands need not be distinct.

The Ramsey number $R(s,t)$ is the smallest integer $N$ such that every red-blue colouring of the edges of $K_N$ has a red $K_s$ or a blue $K_t$. Equivalently, every graph on $N$ vertices contains a clique of size $s$ or an independent set of size $t$.

Set $R(1,t)=R(s,1)=1$. For $s,t\ge 2$, let $N=R(s-1,t)+R(s,t-1)$ and fix a vertex $v$ in a red-blue colouring of $K_N$. Among the remaining $N-1$ vertices, either at least $R(s-1,t)$ are red neighbors of $v$, or at least $R(s,t-1)$ are blue neighbors. In the first case their induced colouring gives a red $K_{s-1}$, which extends with $v$ to a red $K_s$, or a blue $K_t$. The second case is symmetric. This proves the Ramsey number recursionInduction on $s+t$, using the boundary values and Pascal's identity, now gives the binomial upper bound for a Ramsey number:In particular this induction proves that the required Ramsey number exists.

An inclusion-exclusion proof gives the coefficients directly. For an edge set $F\subseteq E(G)$, let $c(F)$ be the number of connected components of the spanning graph $(V(G),F)$, including isolated vertices. Requiring the two endpoints of every edge of $F$ to have the same colour leaves exactly $x^{c(F)}$ colourings. Thus the chromatic polynomial inclusion-exclusion formula isConsider a term with $n-c(F)=i\le k-2$. If $(V(G),F)$ contained a cycle, that cycle would have length at least $k$. The component containing it would have at least $k$ vertices and hence contribute at least $k-1$ to $n-c(F)$, a contradiction. Therefore $F$ is a forest. For a forest, $n-c(F)=|F|$, so necessarily $|F|=i$.

Conversely, every $i$-element edge set with $i\le k-2$ is a forest, since a cycle would require at least $k$ edges. Thus exactly $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ edge sets contribute to the coefficient of $x^{n-i}$, and they all have sign $(-1{)}^i$. ConsequentlyThis proves girth determines initial chromatic coefficients without requiring the suggested double induction.

Induct on the number of edges, allowing coefficients outside the displayed degree range to be zero. An edgeless graph has $p_G(x)=x^n$, so its leading coefficient is $1$ and all others are zero. For an edge $e$, write the alternating coefficients of $G-e$ as $b_i$ and those of the simplified contraction $G/e$ as $c_i$. The deletion-contraction recurrence for the chromatic polynomial giveswith $c_{-1}=0$. Both smaller graphs have fewer edges, so induction gives nonnegative coefficients $b_i,c_i$. Thus $a_i=b_i+c_{i-1}\ge 0$. Moreover $a_0=b_0=1$ andFor a graph with at least one vertex, $p_G(0)=0$, so the constant term vanishes. ThereforeIn the one-vertex case, the coefficient of $x^{n-1}$ is simply zero; this is the same $a_1=m=0$ convention beyond the written summation range.

For a nonnegative integer $q$, the chromatic polynomial $p_G(q)$ counts the proper vertex colourings of $G$ using a fixed set of $q$ colours. In a proper colouring, the endpoints of every edge have different colours. The counting function extends uniquely to a polynomial, as follows either from the recurrence below with the edgeless base case $p_G(x)=x^{|V(G)|}$ or from inclusion-exclusion.

Let $e=uv$. Every proper colouring of $G-e$ falls into exactly one of two classes. If $u$ and $v$ have different colours, it is a proper colouring of $G$. If they have the same colour, identifying $u$ and $v$ gives a proper colouring of the contracted graph $G/e$, and this correspondence is bijective. Parallel edges produced by contraction impose identical conditions and can be suppressed. Hence, at every nonnegative integer $q$,Since polynomials agreeing at infinitely many values agree identically, the deletion-contraction recurrence for the chromatic polynomial isThroughout, the graphs are finite and simple, as in the usual convention for these statements.

Count one copy for each four-element vertex set. It requires six independent edges, soDistinct copies share an edge exactly when their vertex intersection has size two or three. For each first copy, their numbers are $6\left(\genfrac{}{}{0ex}{}{n-4}{2}\right)$ and $4(n-4)$, respectively. The required union then has eleven or nine edges. Hence the ordered Janson dependency sum isFor large $n$, $\mu =\Theta (n^4)$ and $\Delta =\Theta (n^6)$, so $\Delta \ge \mu$ and ${\mu }^2/(2\Delta )\ge a{n}^2$ for some constant $a>0$. The second Janson inequality therefore givesThis is the asserted asymptotic bound. It can also be made valid for every $n\ge 4$ by decreasing $a$ to cover the finitely many smaller values, since each then has probability strictly below one of containing no copy. For $n<4$ the event has probability one and no positive exponential bound of this form can hold.