Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / A (Graph Theory)

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.

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.

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.

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.

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.

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.

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.

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

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.