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

Hall's theorem states that a finite bipartite graph with classes $L,R$ has a matching covering $L$ if and only if $|N(U)|\ge |U|$ for every $U\subseteq L$. Here $N(U)$ is the set of vertices of $R$ adjacent to at least one member of $U$. Necessity follows because matched partners of $U$ are distinct members of $N(U)$.

For sufficiency induct on $|L|$; zero or one vertex is immediate. If a nonempty proper $U\subset L$ has $|N(U)|=|U|$, Hall's condition holds within the graph on $U,N(U)$. It also holds on the remaining classes: for $T\subseteq L\setminus U$,Induction gives matchings in these two disjoint subgraphs, and their union covers $L$. Otherwise every nonempty proper $U$ has $|N(U)|\ge |U|+1$. Choose any edge $lr$ and delete its two endpoints. Every nonempty subset of the remaining left class was a proper subset of $L$, so deleting $r$ leaves at least as many neighbours as vertices. Induction gives a matching there, and adjoining $lr$ completes the matching. This proves sufficiency in all cases.

Make a bipartite graph whose two classes index the two partitions, joining $i$ on the left to $j$ on the right exactly when $A_i\cap B_j\ne \varnothing$. For a subset $U$ of left indices, its union of blocks contains $2008|U|$ elements. They all lie in the blocks indexed by $N(U)$, whose union has $2008|N(U)|$ elements. Thus $|N(U)|\ge |U|$. Hall's theorem gives a matching covering all $n$ left vertices, hence also all $n$ right vertices. Its partner map is the required permutation $\pi$.

In the vertex form of Menger's theorem, for distinct nonadjacent vertices $s,t$ of a finite graph, the maximum number of pairwise internally vertex-disjoint $s$–$t$ paths equals the minimum size of an $s$–$t$ vertex separator. A separator is a subset of vertices other than $s,t$ whose deletion leaves no $s$–$t$ path; internally disjoint paths may share their endpoints but no other vertices. Equivalently, between disjoint vertex sets the maximum number of mutually vertex-disjoint connecting paths equals the minimum size of a separating vertex set, where endpoints may be deleted in that set version.

Add $s$ adjacent to every vertex of $V_1$ and $t$ adjacent to every vertex of $V_2$. Suppose an $s$–$t$ separator $C$ has fewer than $n$ vertices. It cannot contain all of either class. Choose $x\in V_1\setminus C$ and $y\in V_2\setminus C$. No edge can join the remaining two classes, since it would give a three-edge $s$–$t$ path. Hence every neighbour of $x$ lies in $C\cap V_2$, and every neighbour of $y$ lies in $C\cap V_1$. The minimum-degree bound impliesa contradiction. Menger's theorem therefore gives $n$ internally vertex-disjoint $s$–$t$ paths. Each uses at least one vertex of each original class, and only $n$ vertices are available in each class. Every path must consequently use exactly one of each. Their middle edges form a perfect matching.

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.

The Ramsey number $R(s,t)$ is the least $N$ such that every $N$-vertex graph contains a clique of size $s$ or an independent set of size $t$. Take $N=R(s-1,t)+R(s,t-1)$ and choose a vertex $v$. Among its $N-1$ other vertices, either it has at least $R(s-1,t)$ neighbours or it has at least $R(s,t-1)$ nonneighbours.

In the first case those neighbours contain an independent $t$-set or an $(s-1)$-clique, which joins $v$ to form an $s$-clique. In the second case the nonneighbours contain an $s$-clique or an independent $(t-1)$-set, which joins $v$ to form an independent $t$-set. This proves

The five-cycle and its complement both have no triangle, so $R(3,3)>5$. In a six-vertex graph, any vertex has at least three neighbours or three nonneighbours. In the first triple an edge completes a triangle with the chosen vertex, while no edges give an independent triple. The complementary argument handles three nonneighbours. Hence $R(3,3)=6$.

Now suppose a nine-vertex graph contains no triangle and no independent four-set. Each vertex has at most three neighbours, since its neighbourhood is independent. It cannot have at most two neighbours: its at least six nonneighbours contain, by the result just proved, either a triangle or an independent triple; the former is forbidden and the latter joins the vertex to give an independent four-set. Every degree must therefore equal three. But nine vertices of degree three have odd total degree, contradicting the handshake lemma. Thus $R(3,4)\le 9$.

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

Assume the usual nontrivial case $\chi (G)\ge 2$ and $|H|\ge 2$. On $(\chi (G)-1)(|H|-1)$ vertices partition into $\chi (G)-1$ equal classes of size $|H|-1$. Color all edges between distinct classes red and all edges within a class blue. The red graph is $(\chi (G)-1)$-colorable, so it contains no copy of $G$. Every blue connected component has only $|H|-1$ vertices, so connectedness prevents a blue copy of $H$. Therefore one more vertex is necessary:If $G$ is edgeless or $H$ has one vertex, the displayed lower bound is just one and holds directly.

For nonempty disjoint vertex sets, the edge density is $d(X,Y)=e(X,Y)/(|X||Y|)$. A pair is $ϵ$-uniform, also called $ϵ$-regular, if every $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge ϵ|X|$ and $|Y^{\prime }|\ge ϵ|Y|$ satisfiesIt says that restricting to reasonably large subsets does not noticeably change the edge density.

In the standard regularity-partition convention, the vertex sets form a disjoint partition, the nonexceptional sets $V_1,\dots ,V_k$ are nonempty and have a common size, $|V_0|<ϵ|V(G)|$, and at most $ϵk^2$ unordered nonexceptional pairs fail to be $ϵ$-uniform. One can instead use weak inequality for the exceptional-set bound without affecting the argument below once the size bound is strict. The exceptional set absorbs the rounding remainder when the graph order is not divisible by $k$.

Write $N=|G|$ and $D(U)=e(G[U])-p\left(\genfrac{}{}{0ex}{}{|U|}{2}\right)$. For disjoint sets $U,W$ of size at least ${ϵ}^{2}N$, the given identity and the corresponding binomial identity giveIn the nonvacuous regularity range $0<ϵ<1$, the original sets therefore satisfy $|d(X,Y)-p|<{ϵ}^3/3$. Their allowed subsets have size at least ${ϵ}^{2}N$, so $|d(X^{\prime },Y^{\prime })-p|<ϵ/3$. The triangle inequality givesThus the pair is uniform. For $ϵ\ge 1$, the definition is vacuous or immediate; the subsequent positive-integer condition $k<1/ϵ$ has no solutions.

For the partition deduction, choose $k$ equal classes of size $q=\lfloor N/k\rfloor$, putting the remainder into $V_0$. For fixed $k<1/ϵ$ and sufficiently large $N$, $q\ge ϵN$ and $|V_0|<k<ϵN$. Every class pair is uniform by what was just proved, which is stronger than the required condition. For example, it suffices thatA graph-size qualification is necessary if the printed deduction is read literally for every graph order. Under the standard nonempty-class definition, a one-vertex graph satisfies the discrepancy hypothesis for every $p$ and positive $ϵ$, but cannot be partitioned into two nonempty classes even when $2<1/ϵ$. The source omits this small-order qualification. If $k$ divides $N$, no rounding is needed and $N\ge k$ already suffices, since $N/k>ϵN$.