Past exam of the graph theory course of the University of Oxford

Original solutions to past examinations of the graph theory course of the University of Oxford.

Solutions to all three questions of the graph theory course of the University of Oxford Part B examination, sat on 15 June 2023. Source: original released PDF, bundle pages 243–244; paper pages 1–2. Throughout, graphs are finite simple graphs unless a construction explicitly permits parallel edges.

A proper edge colouring assigns colours to the edges of a graph so that distinct edges sharing a vertex have different colours. The edge chromatic number ${\chi }^{\prime }(G)$ is the least number of colours in such an assignment. Equivalently, it is the least number of matchings in a graph whose disjoint union is the entire collection of edges.

Vizing's theorem states that a finite simple graph of maximum degree $\Delta$ satisfiesThe lower bound holds because all edges incident with a vertex of vertex degree $\Delta$ require different colours.

Hall's marriage theorem states that a finite bipartite graph with vertex sets $A,B$ has a matching in a graph saturating $A$ if and only ifwhere $N(S)\subseteq B$ is the graph neighbourhood of $S$. Here matching saturation means that each vertex of $A$ is incident with an edge of the matching in a graph; it does not require every vertex of $B$ to be met.

Let $A_{\Delta }=\{a\in A:d_G(a)=\Delta \}$. Apply Hall's marriage theorem to the induced subgraph on $A_{\Delta }\cup B$, which is a bipartite graph. For any subset $S\subseteq A_{\Delta }$, double counting the edges from $S$ to its graph neighbourhood givesThe equality uses the fact that every neighbour of $S$ lies in $B$, so all edges incident with $S$ have been counted. The final inequality uses the maximum degree bound on $B$. Since $\Delta >0$, division gives the Hall condition $|S|\le |N(S)|$.

Consequently there is a matching in a graph $M_1$ saturating $A_{\Delta }$. If $A_{\Delta }$ is empty, use the empty matching in a graph. This proves the required matching covering maximum-degree vertices in a bipartite graph on the specified side; other vertices need not be met.

By part (i), choose a matching in a graph $M_1$ meeting all vertices of vertex degree $\Delta$ in $A$. Interchanging the two vertex sets gives a matching in a graph $M_2$ meeting all such vertices in $B$. Consider the spanning subgraph $H$ with edges $M_1\cup M_2$.

Every vertex has vertex degree at most two in $H$. An edge belonging to both matchings in a graph forms a whole two-vertex connected component of a graph, since neither endpoint can meet another edge of either matching in a graph. On every other nontrivial connected component of a graph, the edges alternate between $M_1$ and $M_2$, so the connected component of a graph is a graph path or an even graph cycle. We select one of the two matchings in a graph separately on each connected component of a graph.

On a graph cycle, either choice covers every vertex. On a graph path with an odd number of edges, the first and last edges belong to the same matching in a graph; choose it, and it covers every vertex of the graph path. For a common edge, choose that edge.

It remains to treat a graph path with a positive even number of edges. Its endpoints lie in the same side of the bipartite graph. Every internal vertex meets both matchings in a graph. If both endpoints lie in $A$, choose $M_1$: every endpoint of vertex degree $\Delta$ must already be met by $M_1$, by its defining property. If both endpoints lie in $B$, choose $M_2$ for the same reason. Thus the choice meets all vertices of vertex degree $\Delta$ in that connected component of a graph.

Finally, an isolated vertex of $H$ cannot have vertex degree $\Delta$ in $G$, since it would have been met by $M_1$ or $M_2$. The union of the selected edges over the connected components of a graph is a matching in a graph, because different connected components of a graph have disjoint vertex sets. It meets every vertex of vertex degree $\Delta$ in $G$. The useful mechanism is the union of two matchings and its alternating connected components of a graph.

Use mathematical induction on the maximum degree $\Delta$, including $\Delta =0$ as the base case. A graph of maximum degree zero has no edges, so zero colours suffice.

For $\Delta >0$, part (ii) supplies a matching in a graph $M$ meeting every vertex of vertex degree $\Delta$. Delete its edges, retaining all vertices. Each vertex formerly of maximum degree loses one incident edge; every other vertex already had vertex degree at most $\Delta -1$. HenceThe resulting graph is still a bipartite graph. By mathematical induction, it has a proper edge colouring using at most $\Delta -1$ colours. Give every edge of $M$ one new colour. Since $M$ is a matching in a graph, this produces a proper edge colouring of $G$ with at most $\Delta$ colours. The edges at a vertex of maximum degree require at least $\Delta$ colours, soThis is Kőnig's line colouring theorem.

For even $r\ge 2$, take the complete graph $K_{r+1}$. It is an $r$-regular graph on an odd number of vertices. Every matching in a graph has at most $r/2$ edges, so $r$ colours in a proper edge colouring could cover at most $r^2/2$ edges. ButTherefore ${\chi }^{\prime }(K_{r+1})>r$; Vizing's theorem gives ${\chi }^{\prime }(K_{r+1})=r+1$. This includes the graph triangle when $r=2$.

For odd $r\ge 3$, first construct a graph $H_r$ on $r+2$ vertices. Start with the complete graph onand delete the edges $va$, $vb$, and $c_1{c}_2,c_3{c}_4,\dots ,c_{r-2}{c}_{r-1}$. The pairing is possible because $r-1$ is even. In the initial complete graph, every vertex has vertex degree $r+1$. The distinguished vertex $v$ loses two edges and every other vertex loses exactly one, givingTake two disjoint copies of $H_r$, with distinguished vertices $v,v^{\prime }$, and add the edge $v{v}^{\prime }$. The resulting simple graph $G_r$ is an $r$-regular graph. The added edge is the only edge between the two copies; each copy has the odd number $r+2$ of vertices.

Suppose an $r$-colour proper edge colouring existed. At each vertex, the $r$ incident edges would use all $r$ colours. Thus each colour would form a perfect matching. Any perfect matching must use $v{v}^{\prime }$: without it, each odd-sized copy would have to be covered by internal pairs, which is impossible by parity. Therefore all $r$ colour classes would have to contain the same edge $v{v}^{\prime }$, a contradiction. Hence Vizing's theorem again givesThese constructions give class two regular graphs for every $r\ge 2$. The odd-$r$ construction exhibits the bridge obstruction to regular edge colouring; $H_r$ is a connected graph because every vertex other than $a,b,v$ is adjacent to $v$, while $a,b$ are adjacent to those vertices.

For a finite graph $G$, its chromatic polynomial $p_G(x)$ is the polynomial whose value at each positive integer $q$ counts proper vertex colourings of $G$ from a fixed palette of $q$ labelled colours. Adjacent vertices must receive different colours, and unused colours are allowed.

For an edge $e=uv$, the deletion-contraction recurrence for the chromatic polynomial isHere $G-e$ deletes only the edge $e$, while $G/e$ performs edge contraction, identifying $u,v$ and removing $e$. Any parallel edges produced by edge contraction can be replaced by a single edge, since their constraints on proper vertex colourings are identical.

Indeed, the proper vertex colourings of $G-e$ in which $u,v$ differ are precisely those of $G$, while those in which $u,v$ agree correspond bijectively to proper vertex colourings of $G/e$. This proves the equality for every positive integer $q$, hence as a polynomial identity. Together with $p_G(x)=x^{|V(G)|}$ for a graph without edges, the recurrence also proves by mathematical induction that the counting function is a polynomial.

Let the nonempty connected components of a graph of $G$ be $G_1,\dots ,G_t$. A proper vertex colouring can be chosen separately on each connected component of a graph, since no edge joins different connected components of a graph. The multiplication principle gives, first at positive integers and then as a polynomial identity,It remains to justify that every factor has zero constant term. More generally, for every nonempty simple graph $H$, prove $p_H(0)=0$ by mathematical induction on the number of edges. If there are no edges, then $p_H(x)=x^{|V(H)|}$ with $|V(H)|\ge 1$. Otherwise choose an edge $e$. Both $H-e$ and the simplified edge contraction $H/e$ are nonempty graphs with fewer edges. The deletion-contraction recurrence for the chromatic polynomial and mathematical induction giveThus $p_{G_j}(x)=x{q}_j(x)$ for a polynomial $q_j$, andFor the empty graph, $t=0$ and $p_G(x)=1$, so the conclusion also holds. This is the chromatic polynomial product over components.

Write $V=V(G)$ and $E=E(G)$. For $F\subseteq E$, let $c(F)$ denote the number of connected components of a graph of the spanning subgraph $(V,F)$, including isolated vertices. The inclusion-exclusion principle, applied to the unwanted events that the two endpoints of an edge receive the same colour, gives the chromatic polynomial inclusion-exclusion formulaTo justify the exponent, imposing equal colours across all edges in $F$ forces a single colour on each connected component of a graph of $(V,F)$, with independent choices between its connected components of a graph. Thus the corresponding count at $q$ colours is $q^{c(F)}$. Equality for all positive integers proves the polynomial identity.

Fix an index $i$ in the stated range. A subset $F$ contributes to the coefficient of $x^{n-i}$ exactly when $n-c(F)=i$. If $(V,F)$ contains a graph cycle of length $s$, the hypothesis gives $s\ge \ell$. All its $s$ vertices lie in one connected component of a graph. For any connected component of a graph $D$, its contribution to $n-c(F)$ is $|V(D)|-1$, soThis contradicts $i\le \ell -2$. Therefore every contributing $(V,F)$ is a forest. The forest identity $|F|=n-c(F)$ then gives $|F|=i$.

Conversely, every $i$-edge subset is a forest, since a graph cycle in it would have at most $i<\ell$ edges. It therefore has $c(F)=n-i$ and contributes exactly $(-1{)}^i$. There are $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ such subsets, by the definition of a binomial coefficient. ConsequentlyHere the coefficient notation is understood within the defined indices $0\le i\le n$; if the displayed range is extended past $n$, the coefficients beyond the constant term can be set to zero. For a forest, $m\le n-1$, so the binomial coefficients there are also zero. The key reason girth determines initial chromatic coefficients is that a graph cycle can affect only exponents whose loss of connected components of a graph is at least $\ell -1$.

First reduce the unicyclic graph to its unique graph cycle $C$. Delete the edges of $C$ but retain every vertex. The remaining graph is a forest, since any surviving graph cycle would be a second one in $G$. Each of its connected components of a graph contains a vertex of $C$: follow a graph path to $C$ in the original connected graph, stopping at the first vertex of $C$; this initial segment uses no edge of $C$.

No such connected component of a graph contains two vertices of $C$. Otherwise, on the tree graph path between them, choose two successive visits to $C$. The segment between these visits has no internal vertex on $C$ and uses no edge of $C$. Combining it with either connecting arc of $C$ gives a second graph cycle, a contradiction. Thus the remaining graph consists of trees, each rooted at exactly one vertex of $C$.

After choosing a proper vertex colouring of $C$ from $q$ colours, colour these rooted trees away from their roots. Each of the $n-\ell$ off-graph cycle vertices has one already coloured parent in a rooted tree, leaving exactly $q-1$ choices. The multiplication principle therefore givesEquivalently, this repeatedly applies the chromatic polynomial after attaching a leaf formula.

To compute the chromatic polynomial of a cycle, the base case is the graph triangle:For $s\ge 4$, deleting a cycle graph edge gives a path graph on $s$ vertices, while edge contraction gives $C_{s-1}$. The chromatic polynomial of that path graph is $x(x-1{)}^{s-1}$, by choosing the colour of its first vertex and then each successive vertex. Hence the deletion-contraction recurrence for the chromatic polynomial givesUsing mathematical induction, substitute $p_{C_{s-1}}(x)=(x-1{)}^{s-1}+(-1{)}^{s-1}(x-1)$ to obtainMultiplying by the factor for the attached trees proves the chromatic polynomial of a unicyclic graph formula

A graph is a k-connected graph if it has at least $k+1$ vertices and deleting any set of fewer than $k$ vertices, together with their incident edges, leaves a connected graph.

The vertex connectivity $\kappa (G)$ is the largest such $k$. Equivalently, for a graph with at least two vertices, it is the smallest number of vertices whose deletion either disconnects the graph or leaves a single vertex. The latter convention gives $\kappa (K_n)=n-1$ for a complete graph. A disconnected graph has vertex connectivity zero; one usually also sets $\kappa (K_1)=0$.

For distinct nonadjacent vertices $x,y$, the local connectivity isSuch a set $S$ is an $x$–$y$ vertex separator. By Menger's theorem, local connectivity also equals the maximum number of internally vertex-disjoint paths from $x$ to $y$. If no graph path exists already, the empty vertex separator gives zero.

The vertex separator version of Menger's theorem says that, for distinct nonadjacent vertices $x,y$ of a finite graph, the maximum number of internally vertex-disjoint paths from $x$ to $y$ equals the minimum size of an $x$–$y$ vertex separator.

Use the following version of the max-flow min-cut theorem: in a finite directed flow network with nonnegative integer flow network edge capacities, the maximum flow value equals the minimum cut capacity, and a maximum flow can be chosen to have integer values on every directed edge. The last clause is the integral max-flow theorem.

Here is the reduction, including the correspondence with vertex separators. Put $N=|V(G)|$. Perform vertex splitting on each vertex $v\ne x,y$, replacing it by $v_{\mathrm{in}},v_{\mathrm{out}}$ with a directed edge $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of flow network edge capacity one. Keep $x$ as the source and $y$ as the sink. For each original undirected edge $uv$, put directed edges from the output of $u$ to the input of $v$ and from the output of $v$ to the input of $u$, each of flow network edge capacity $N$; an unsplit endpoint uses $x$ or $y$ itself.

A family of $p$ internally vertex-disjoint paths gives a feasible integral flow of value $p$, by sending one unit down each graph path. Conversely, decompose an integral flow into unit source-to-sink graph paths and directed cycles, discarding the directed cycles. This decomposition can be obtained by following positive-flow directed edges and subtracting one unit along a source-to-sink graph path or a directed cycle, repeating until the flow value is exhausted. A capacity-one split edge can belong to at most one unit graph path. The projected graph paths in $G$ are therefore internally vertex-disjoint paths. Thus the largest number of such graph paths equals the maximum flow value.

Deleting a vertex separator $S$ corresponds to removing its split edges, of total flow network edge capacity $|S|$. This destroys every source-to-sink graph path; taking the source-reachable vertices after removal gives a cut of a flow network of cut capacity at most $|S|$. Thus the minimum cut capacity is no greater than the minimum vertex separator size.

For the reverse inequality, deleting all $N-2$ internal vertices separates $x,y$, because they are nonadjacent. Hence a minimum cut has cut capacity at most $N-2<N$ and cannot contain a directed edge of flow network edge capacity $N$. Its outgoing edges are therefore split edges. Let $S$ be the original vertices associated with them. Any $x$–$y$ graph path avoiding $S$ would lift to a source-to-sink graph path crossing this cut of a flow network without using an outgoing edge, an impossibility. Hence $S$ is a vertex separator, with size exactly the cut capacity. The two minima agree, and the max-flow min-cut theorem proves Menger's theorem.

Add two new vertices $s,t$ to $G$, joining $s$ to every vertex of $U$ and $t$ to every vertex of $W$, with no other new edges. The vertices $s,t$ are nonadjacent. Suppose $S\subseteq V(G)$ has $|S|<k$. Since $G$ is a k-connected graph, $G-S$ is a connected graph. Both $U\setminus S$ and $W\setminus S$ are nonempty because each original set has cardinality $k$. Choose $u\in U\setminus S$ and $w\in W\setminus S$; a graph path between them in $G-S$ extends to an $s$–$t$ graph path avoiding $S$.

Consequently no fewer than $k$ vertices can form an $s$–$t$ vertex separator. By Menger's theorem, there are at least $k$ internally vertex-disjoint paths from $s$ to $t$. There cannot be more than $k$, since $s$ has only $k$ neighbours.

Remove $s,t$ from these $k$ graph paths. The resulting graph paths in $G$ start at distinct vertices of $U$, end at distinct vertices of $W$, and are pairwise vertex-disjoint paths: any shared vertex would have been an internal vertex common to two of the original graph paths. Because there are exactly $k$ graph paths, they use every vertex of $U$ and $W$ as an endpoint. None can pass through another terminal internally, since that terminal already occurs as an endpoint of one of the vertex-disjoint paths. Thus there are $k$ vertex-disjoint paths from $U$ to $W$, with some pairing of the endpoints. This is also an immediate application of the Set version of Menger theorem.

No. A counterexample works for every $k\ge 2$. Take the complete bipartite graph $G=K_{k,k}$ with vertex setsIt is a k-connected graph: deleting fewer than $k$ vertices leaves at least one vertex in each side, and the remaining complete bipartite graph is a connected graph.

Chooseand order these sets so that $u_1=b_1$ and $w_1=b_2$. Order the other members arbitrarily. These are disjoint sets of cardinality $k$, and every vertex of $G$ is one of the specified endpoints.

If the prescribed $k$ vertex-disjoint paths existed, no one of them could have an internal vertex, because every vertex must serve as the endpoint of one of the graph paths. Thus each graph path would have to be a single edge. But $b_1,b_2$ lie in the same side of the bipartite graph, so there is no edge $b_1{b}_2$. This contradicts the requirement on $P_1$.

For $k=2$ this is the four-vertex cycle graph, with opposite vertices paired. The stronger property that every prescribed pairing can be realized is the linked graph property; vertex connectivity alone does not guarantee it.

We verify the Hall condition for $U$. Let $S\subseteq U$. If $S$ is empty, then $|N(S)|=0=|S|$. Suppose $0<|S|\le n/2$. Choose $u\in S$. Its graph neighbourhood is contained in $N(S)$, so the minimum degree hypothesis givesIf $|S|>n/2$, suppose for a contradiction that some vertex $w\in W\setminus N(S)$ exists. All neighbours of $w$ lie in $U\setminus S$, socontradicting the minimum degree hypothesis. Thus $N(S)=W$ and $|N(S)|=n\ge |S|$.

Every subset $S\subseteq U$ satisfies the Hall condition. By Hall's marriage theorem, there is a matching in a graph saturating $U$. Since $|U|=|W|=n$, its $n$ edges also cover every vertex of $W$. It is therefore a complete matching, meaning a perfect matching. For $n=0$, the empty matching in a graph already has this property.

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.