Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / A / 2

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.

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.

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.

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}$.

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.