Past exam of the graph theory course of the University of Oxford / 2011 (C11.1a, DMAC 2A85, DMCO 2A85, DMSU 2A85)

Source paper: FOI request thread. The intact cover identifies Graph Theory, C11.1a, Friday 10 June 2011, 9.30am to 11.00am. This three-page paper occupies original private-bundle pages 466–468. Its three questions match Section A of the separately issued combined Graph Theory and Probabilistic Combinatorics paper, C11.1; the same solution bodies are reused here under this paper's own question tree.

The Ramsey number $R(s,t)$ is the least integer $N$ such that every graph on $N$ vertices contains either a clique of size $s$ or an independent set of size $t$. Equivalently, every red-blue colouring of the edges of $K_N$ contains a red $K_s$ or a blue $K_t$.

Put $a=R(s-1,t)$, $b=R(s,t-1)$ and consider a graph on $a+b$ vertices. Fix a vertex $v$. If it has at least $a$ neighbours, their induced graph contains either a clique of size $s-1$, which together with $v$ gives a clique of size $s$, or an independent set of size $t$. Otherwise $v$ has at least $b$ nonneighbours. Their induced graph contains either a clique of size $s$, or an independent set of size $t-1$, which can be enlarged by $v$. ThusSince $R(2,3)=R(3,2)=3$, this gives $R(3,3)\le 6$. For the reverse bound, the five-cycle has no triangle and no independent set of size three: its complement is again a five-cycle, so it too is triangle-free. Hence the property fails on five vertices and

The vertex version of Menger's theorem states that for two distinct nonadjacent vertices $s,t$ of a finite graph, the maximum number of internally vertex-disjoint $s$-$t$ graph paths equals the minimum size of a set $S\subseteq V\setminus \{s,t\}$ whose deletion separates $s$ from $t$.Internally disjoint graph paths may share their endpoints but no other vertex. The nonadjacency hypothesis is needed in this separator formulation, since an edge $st$ cannot be destroyed by deleting other vertices.

Let the bipartition be $L\cup R$. Form an auxiliary graph by adding a new vertex $s$ adjacent to every vertex of $L$ and a new vertex $t$ adjacent to every vertex of $R$. The vertices $s,t$ are nonadjacent, so Menger's theorem applies.

A matching of size $m$ gives $m$ internally disjoint graph paths $s\ell rt$, one for each matching edge $\ell r$. Conversely, every $s$-$t$ graph path must use an edge of the original bipartite graph. Choose one such edge from each member of an internally disjoint family. Their endpoints are all distinct, so the chosen edges form a matching. Thus the maximum number of those graph paths is the maximum matching size.

An $s$-$t$ separator contained in $L\cup R$ is exactly a vertex cover of the original graph. Indeed, an uncovered edge $\ell r$ would leave the graph path $s\ell rt$, while removing a vertex cover removes every edge between $L$ and $R$ and hence every $s$-$t$ graph path. The minimum separator size is therefore the minimum vertex cover size. Menger givesThis is Kőnig's theorem for bipartite matching. The auxiliary construction gives the required deduction from vertex-disjoint paths rather than assuming a matching theorem in advance.

Hall's marriage theorem says that a bipartite graph with parts $L,R$ has a matching saturating $L$ if and only ifNecessity follows because the matched neighbours of vertices of $S$ are distinct and belong to $N(S)$.

For sufficiency, assume these inequalities. Let $K=U\cup W$ be any vertex cover, with $U\subseteq L$ and $W\subseteq R$. Every neighbour of $S=L\setminus U$ must belong to $W$, since otherwise its edge from $S$ is uncovered. Therefore $|W|\ge |N(S)|\ge |S|$, and $|K|\ge |U|+|S|=|L|$. The whole part $L$ is itself a vertex cover of size $|L|$. Part (ii) now gives a matching of size exactly $|L|$, so it saturates $L$.

Choose a spanning tree of the connected graph and root it at $x$. List vertices in nonincreasing order of their distance from $x$ in this tree, breaking ties arbitrarily. The root has distance zero and is last, so $v_n=x$.

Every other vertex has a parent one step closer to the root. That parent is adjacent to it and appears later in the ordering. HenceFor a graph of one vertex the condition is vacuous and the same ordering works.

Write $\Delta =\Delta (G)$, which is at least two because $x$ has the two specified neighbours. Give $y$ and $z$ the same colour, say colour one; this is proper because they are nonadjacent.

Apply part (i) to the connected graph $G\setminus \{y,z\}$, with $x$ last. Colour its vertices greedily in the resulting order using a palette of $\Delta$ colours. Every vertex before $x$ has a neighbour later in this order, so at most $\mathrm{deg}(v)-1\le \Delta -1$ of its neighbours have already received colours. At least one palette colour is available.

When $x$ is reached, all its neighbours are coloured, but the two neighbours $y,z$ have the same colour. Thus there are at most $\mathrm{deg}(x)-1\le \Delta -1$ distinct forbidden colours. Colour $x$ with a remaining one. This constructs a proper colouring withThe common colour on the two initial vertices replaces the usual need for an uncoloured neighbour at the last greedy step.

This is greedy colouring with two precoloured neighbours.

Take a proper colouring $c:V(G)\to \{1,\dots ,k\}$ and orient every edge from its lower-coloured endpoint towards its higher-coloured endpoint. Along a directed path the colour strictly increases, so such a graph path has at most $k$ vertices. A directed cycle is impossible for the same reason. Thus

For each vertex $v$, let $c(v)$ be the maximum number of vertices in a directed path ending at $v$. These numbers lie between one and $\ell$.

If $u\to v$ is an edge, a longest graph path ending at $u$ cannot already contain $v$, since that would give a directed cycle on appending $u\to v$. Appending it therefore creates a graph path ending at $v$, so $c(v)\ge c(u)+1$. Adjacent vertices consequently receive different colours. HenceAcyclicity is exactly what justifies extending the graph path without repeating a vertex.

Part (ii) shows that $\chi (G)\le \lambda (D)$ for every acyclic orientation $D$, so $\chi (G)$ is at most their minimum. Part (i), applied to an optimal colouring, supplies an acyclic orientation with $\lambda (D)\le \chi (G)$. Combining the inequalities givesThe parameter counts vertices on a graph path; if graph path length were instead counted in edges, the corresponding minimum would be $\chi (G)-1$.

These constructions prove chromatic number from acyclic longest paths.

Fix a proper colouring with exactly $k$ nonempty colour classes. For any class $C_i$, suppose every vertex in it misses at least one of the other $k-1$ colours in its neighbourhood. Recolour each of these vertices by one of its missing colours. No edge joins two vertices of $C_i$, so these simultaneous recolourings cannot conflict with one another, and the chosen colours do not conflict with vertices outside $C_i$.

This would eliminate colour $i$ and produce a $(k-1)$-colouring, contradicting optimality. Therefore each colour class contains a vertex adjacent to at least one vertex of every other colour. That vertex has degree at least $k-1$. Choosing one from each class gives $k$ distinct vertices, provingFor $k=1$, a nonempty graph already has a vertex of degree at least zero, so the conclusion holds as well.

For disjoint nonempty sets $X,Y$, let $e(X,Y)$ count edges between them. Their edge density isThe pair is $\epsilon$-regular if every $A\subseteq X$ and $B\subseteq Y$ with $|A|\ge \epsilon |X|$, $|B|\ge \epsilon |Y|$ satisfies $|d(A,B)-d(X,Y)|\le \epsilon$.

An $\epsilon$-regular partition has disjoint classes $V_0,V_1,\dots ,V_k$ covering $V(G)$, with $|V_0|\le \epsilon |V(G)|$, equal positive sizes $|V_1|=\cdots =|V_k|$, and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$ with $1\le i<j\le k$ that are not $\epsilon$-regular. The set $V_0$ is exceptional and its pairs need not satisfy regularity.

Szemerédi regularity lemma states that for every $\epsilon >0$ and integer $m_0\ge 1$, there are integers $M,n_0$ such that every graph with $n\ge n_0$ vertices has such a partition withThe bounds depend on $\epsilon ,m_0$, not on the graph order. Using a strict regularity inequality or a slightly different constant in the allowed pair count gives an equivalent conventional version; the displayed convention will be used below.

Let $B\subseteq X$ be the vertices with fewer than $(d/2)|Y|$ neighbours in $Y$. If $|B|\ge \epsilon |X|$, regularity applies to the pair $(B,Y)$ and givesBut averaging the defining strict degree inequality over $B$ gives $d(B,Y)<d/2$, a contradiction. ThereforeRegularity controls the neighbourhood of almost every vertex because a large set of exceptional low-degree vertices would itself witness an irregular density.

Apply part (b) to $(X_1,X_2)$ and $(X_1,X_3)$. Fewer than $2\epsilon |X_1|$ vertices fail at least one of the degree bounds. For any remaining vertex $v$, put $N_2=N(v)\cap X_2$ and $N_3=N(v)\cap X_3$. ThenRegularity of $(X_2,X_3)$ gives $d(N_2,N_3)\ge d-\epsilon \ge d/2$. Every edge between $N_2$ and $N_3$ makes a distinct triangle containing $v$. Hence $v$ belongs to at leastsuch triangles. This proves the asserted bound on exceptional vertices.

There are at least $(1-2\epsilon )|X_1|\ge |X_1|/2$ good vertices. Summing their triangle counts counts each triangle with one vertex in each cluster exactly once, at its $X_1$ vertex. ThereforeThere is no factor of three to divide out in this cross-cluster count.

This is the regular triangle counting lemma with explicit coarse constants.

Choose a small density threshold $d>0$, then $\epsilon \le \min (d/2,1/4)$ sufficiently small and a lower partition bound $m_0$ sufficiently large thatApply the regularity lemma. Delete all edges incident with $V_0$, all edges within a class $V_i$, all edges between irregular pairs, and all edges between regular pairs of density below $d$. Their total is at mostIf a triangle remains, its vertices lie in three distinct nonexceptional classes, all whose pairs were regular with original density at least $d$. Part (c) then forces at least $(d^3/16)t^3$ triangles in the original graph, where $t$ is the common class size. Since $k\le M$ and $\epsilon \le 1/4$, we have $t\ge n/(2M)$, so this is at least $d^3{n}^3/(128M^3)$.

Choose $c=d^3/(256M^3)$ and take $n_0$ large enough for the regularity lemma. An original graph with at most $c{n}^3$ triangles cannot leave any triangle after these deletions. Thus deleting at most $\eta n^2$ edges makes the graph triangle-free. This is the triangle removal lemma; boundedly many large regular clusters turn any surviving triangle into a positive-density family of original triangles.