Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / B / 5

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.

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.

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.