For a variable $Z$ of finite variance and $t>0$, Chebyshev's inequality isOn that event, $(Z-EZ{)}^2\ge t^2$. Thus $t^{2}P(|Z-EZ|\ge t)\le E[(Z-EZ{)}^2]$, proving the assertion. Equivalently apply Markov's inequality to the squared deviation.

From every vertex choose one neighbour of the successor color and follow these choices. The finite directed graph with one chosen outgoing edge per vertex contains a directed cycle. Its vertices are distinct until the first repeated vertex. Each step increases the color by one modulo five, so returning to the starting vertex requires the cycle length to be divisible by five. It therefore has length at least five and is also a cycle in the underlying graph. This proves a cycle of length a positive multiple of five exists.

Assign each vertex a color independently and uniformly from the five available residues. Let $A_v$ be the event that none of its neighbours has the successor color. Conditional on the color of $v$, its $r$ neighbours all avoid that color with probability $(4/5{)}^r$, so $P(A_v)=(4/5{)}^r$.

The event only uses colors in the closed neighbourhood of $v$. Events based on disjoint such sets are jointly independent. A closed neighbourhood can intersect another only when the two centres are at distance at most two, giving dependency degree at most $r+r(r-1)=r^2$. For sufficiently large $r$,The symmetric local lemma therefore supplies a color assignment with no bad event, proving every vertex has a neighbour of the successor color. As defined in the question, this is a five-color assignment; it is not required to be a proper vertex coloring of every edge, which would be impossible for some large regular graphs.

The construction generalizes to cyclic successor colorings of regular graphs.

For events $A_i$ with a dependency graph, assume each event is independent of the sigma-algebra generated by its nonneighbours. If numbers $x_i\in [0,1)$ satisfy $P(A_i)\le x_i{\prod }_{j\in \Gamma (i)}(1-x_j)$, the general Lovász local lemma givesThe symmetric version says that if every event has probability at most $q$, the dependency graph has maximum degree at most $d$, and $eq(d+1)\le 1$, then none occurs with positive probability. For $d\ge 1$, set $x_i=1/(d+1)$. Since $(1-1/(d+1){)}^d\ge e^{-1}$, the general condition follows from the symmetric numerical hypothesis. The logarithmic inequality $\log (1+1/d)\le 1/d$ proves that estimate. When $d=0$, the events are mutually independent and each has probability below one, so the conclusion is immediate. This is the intended implication from the general to the symmetric form; the source repeats the word symmetric in its final clause.

Retain $0<ϵ<d/2$ from the preceding part. In $X_1$, at most $ϵn$ vertices have too few neighbours in $X_2$, and at most $ϵn$ have too few in $X_3$. Since $d\le 1$, $2ϵ<1$, so some $x\in X_1$ is good for both. Put $Y_2=N(x)\cap X_2$ and $Y_3=N(x)\cap X_3$. Their sizes are at least $dn/2>ϵn$. Regularity of $(X_2,X_3)$ therefore givesThere is an edge joining a vertex of $Y_2$ to a vertex of $Y_3$. Its two endpoints and $x$ form a triangle. The nonempty equal classes ensure this counting argument also covers small integer sizes.

Let $S$ be the vertices of $X$ with fewer than $d|Y|/2$ neighbours in $Y$. If $|S|>ϵn$, it is a permissible subset in the regularity test, and averaging those degrees gives $d(S,Y)<d/2$. But $d(X,Y)\ge d$, socontradicting regularity. Therefore there are at most $ϵn$ such vertices. The same argument in fact rules out $|S|\ge ϵn$ when that threshold is integral and nonzero.

For nonempty disjoint vertex sets define $d(X,Y)=e(X,Y)/(|X||Y|)$. The pair is $ϵ$-uniform, also called regular, if whenever $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ have sizes at least $ϵ|X|$ and $ϵ|Y|$,Thus reasonably large relative subsets retain almost the same edge density.

An even cycle is bipartite and has chromatic number two. An odd cycle has chromatic number three. The extremal-density theorem therefore givesFor odd cycles the complete balanced bipartite graph also exhibits the matching asymptotic lower density one half.

The extremal number $\mathrm{ex}(n;H)$ is the maximum number of edges in a simple graph on $n$ vertices containing no subgraph isomorphic to $H$. For a fixed graph with $\chi (H)=r\ge 2$, the Erdős-Stone theorem givesEquivalently, the ratio to $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ tends to $1-1/(r-1)$. The bipartite case has limiting density zero.

A vertex with at least $R(t,t)$ neighbours has either a $t$-clique among them, producing $K_{t+1}$ with the vertex, or an independent $t$-set among them, producing an induced star with that centre.

For the second assertion put $D=R(t,t)-1$. If either of those two outcomes is absent, the preceding result forces maximum degree at most $D$. In a connected graph of this maximum degree, a ball of radius $t-1$ has at most $1+D+\cdots +D^{t-1}$ vertices, using the rough bound on walks at each distance. If the graph has more vertices, some vertex lies at distance at least $t$ from a chosen root. A shortest path to it is induced, since a chord would shorten it; its first $t$ edges give an induced path of the required length. Thus a sufficiently large connected graph has one of the three listed configurations.

For $s,t\ge 2$, split $(s-1)(t-1)$ vertices into $s-1$ classes of size $t-1$, coloring edges between classes red and edges inside classes blue. The red graph has no $K_s$, and every blue component is too small for the connected tree. This proves the lower bound.

For the upper bound let $N=(s-1)(t-1)+1$ and suppose the blue graph contains no copy of the tree. By the permitted chromatic-number statement, its chromatic number is at most $t-1$. A graph of larger chromatic number would have a subgraph of chromatic number exactly $t$, obtained by deleting vertices until that number is reached. A proper blue coloring with at most $t-1$ classes puts no blue edges within any class, so each class is a red clique. If there is no red $K_s$, each class has at most $s-1$ vertices, contradicting $N>(s-1)(t-1)$. ThereforeThe one-vertex boundary cases give one directly.

The graph Ramsey number $R(G,H)$ is the smallest $N$ such that every red-blue coloring of the edges of $K_N$ has a red copy of $G$ or a blue copy of $H$. These copies are subgraphs, not necessarily induced. Equivalently every graph on $N$ vertices contains $G$ or its complement contains $H$.

The Ramsey number $R(k,l)$ is the least $N$ such that every graph on $N$ vertices has a $k$-clique or an independent set of size $l$. Choose a vertex in a graph of order $R(k-1,l)+R(k,l-1)$. It has either at least $R(k-1,l)$ neighbours or at least $R(k,l-1)$ nonneighbours. In the first set, a $(k-1)$-clique extends with the vertex to a $k$-clique, while an independent $l$-set already suffices. The complementary argument handles the second set. ThusThe boundary values are $R(k,2)=k$ and $R(2,l)=l$. Induction on $k+l$, using Pascal's identity, therefore gives

Choose the central vertex's color in $x$ ways. Every rim vertex must avoid that color, so the rim is a cycle colored using the remaining $x-1$ colors. Hence

For a triangle, $p_{C_3}=x(x-1)(x-2)=(x-1{)}^3-(x-1)$. For $n\ge 4$, deleting an edge leaves a path with polynomial $x(x-1{)}^{n-1}$, and contracting it leaves $C_{n-1}$. Deletion-contraction and induction giveThe path formula chooses its first color freely and each succeeding color in $x-1$ ways.

For an edge $e=uv$, colorings of $G-e$ divide into those giving $u,v$ different colors, counted by $p_G$, and those giving them the same color, counted by $p_{G/e}$. Parallel edges produced by contraction may be suppressed. ThusFor an edgeless graph on $n\ge 1$ vertices, $p_G=x^n$. Induct on the number of edges, allowing smaller vertex counts for contractions. If both smaller expansions have alternating nonnegative coefficients, the contraction's leading degree is one lower, so subtracting it giveswith absent coefficients interpreted as zero. Each coefficient remains nonnegative. Both terms have zero constant coefficient for nonempty graphs, so the resulting expansion isThis induction simultaneously proves the counting function is a polynomial.

For a positive integer $x$, the chromatic polynomial $p_G(x)$ counts proper vertex colorings from a palette of $x$ labelled colors, where adjacent vertices must have different colors. The counting function agrees with a polynomial, as proved by deletion-contraction in the next part.

First the graph is connected: every component has at least $\delta (G)+1>n/2$ vertices, so two components cannot fit. Take a longest path $v_1,\dots ,v_k$. Every neighbour of either endpoint lies on that path. In the index set $\{1,\dots ,k-1\}$ defineTheir sizes sum to $d(v_1)+d(v_k)\ge n>k-1$, so they share an index $i$. The edges at that index give the cyclecontaining every vertex of the path. The minimum-degree assumption and $n\ge 3$ ensure the resulting cycle is nondegenerate. If it omitted any graph vertex, connectedness would supply an edge from outside it to the cycle. Starting with that outside vertex and then following the cycle without closing it gives a path with $k+1$ vertices, contradicting maximality. Thus the cycle is Hamiltonian. This proves Dirac's theorem in the required case.

If no complete matching exists, Hall's theorem gives a nonempty $S\subseteq V_1$, of size $k$, with $|N(S)|\le k-1$. The pairs between $S$ and $V_2\setminus N(S)$ must be nonedges, so there are at leastmissing edges. Hence $e(G)\le n^2-n$, contradicting the strict edge bound. Therefore a complete matching exists.

The strictness is necessary: isolate one vertex of $V_1$ and put all edges between the remaining $n-1$ left vertices and all $n$ right vertices. There are exactly $n(n-1)$ edges and no matching can cover the isolated vertex. This also handles $n=1$.

Hall's theorem states that a finite bipartite graph with classes $L,R$ has a matching covering $L$ exactly when $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because the distinct matched partners of $S$ belong to $N(S)$.

For sufficiency take a maximum matching. If it leaves $x\in L$ unmatched, explore alternating paths starting at $x$, traversing unmatched edges from left to right and matched edges back to the left. No reached right vertex can be unmatched, since flipping the edges of such an alternating path would augment the matching. Let $S,T$ be the reached left and right sets. Every neighbour of $S$ lies in $T$: unmatched edges are explored, and a matched edge from a reached left vertex leads to its already reached predecessor. Conversely every member of $T$ is a neighbour of $S$. Their matched partners are exactly $S\setminus \{x\}$, so $|N(S)|=|T|=|S|-1$, contradicting the hypothesis. Thus a matching covering $L$ exists.