Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 110 1 Solution Created 2026-10-03 Updated 2026-10-14
The Erdős-Stone theorem says that, for a fixed graph with chromatic number ,The lower bound comes from the balanced Turán graph with parts; the theorem supplies the matching asymptotic upper bound. Here and below, all forbidden graphs and blow-up parameters are fixed as .
First obtain an almost spanning, almost complete multipartite core. Put . We give the stability argument, rather than infer pointwise degree bounds by differentiating an asymptotic edge-count formula. Suppose first .
We need two elementary ingredients. First, positive homomorphism density of forces a fixed complete multipartite graph . To see this, perform vertex cloning in a graph, replacing one vertex by independent twins. Conditional on the images of the other vertices, its contribution to the homomorphism density changes from a number to ; Jensen inequality gives . Duplicating each original vertex therefore givesA positive lower bound on the right supplies a positive proportion of all maps of the blow-up. Only maps fail to be injective, so for large at least one map is an embedding. Consequently a -free sequence has copies of . The clique removal lemma, proved in the next solution, then deletes edges to give a -free graph with .
Second, we prove the required stability for -free graphs by induction on . For such a graph is edgeless. In an -vertex -free graph , take a vertex of maximum vertex degree , put and , and note that is -free. The Turan theorem and the maximum-degree bound giveIf , both nonnegative error terms are : and . The deficit in the bound for is likewise . Induction partitions into classes with a total of internal edges; adjoining gives an -class partition with the same property. Applying this to and restoring the removed edges gives such a partition of .
The number of possible crossing edges is . Since the actual crossing-edge count is within of this maximum, for every , and there are missing crossing edges. Choose so slowly that the number of vertices missing more than neighbours in other classes is . Delete those vertices and all internal edges. The remaining r-partite graph has vertices and every vertex has crossing vertex degree at least . The Turan theorem, or the size of a largest part, supplies the matching upper bound for its minimum vertex degree. ThusThis is a high-minimum-degree multipartite stability subgraph. The subgraph need not be spanning; deleting the exceptional vertices is essential. For , the spanning edgeless subgraph already proves the assertion.
Extremality forces the minimum degree. Choose . A proper -graph colouring embeds in , so every -free is also -free. By the Erdős-Stone theorem, its extremal edge count has the needed asymptotic size. The preceding proof supplies core classes of size in which every vertex misses only crossing neighbours, uniformly over the core.
Delete an arbitrary vertex from and introduce a new vertex adjacent precisely to with removed if necessary. The new graph is still -free. Indeed any new copy would use , all its neighbours in that copy would be in the specified core classes, and their set of common neighbours in has size . A vertex of this common neighbourhood outside the bounded vertex set of the copy replaces , producing an existing copy of in , a contradiction. For the new vertex is isolated and the same conclusion is immediate.
The replacement adds edges. Since has the maximum possible number of edges, . As was arbitrary and the minimum vertex degree is at most the average vertex degree,This proves the minimum degree of an extremal forbidden-subgraph graph. The replacement argument avoids the invalid implication based solely on the asymptotic formula.
A colour-critical vertex also bounds the maximum degree. Suppose a vertex of has for some fixed . Since the core omits only vertices and all its classes have size , has at least neighbours in each . Otherwise, even counting every vertex in all other classes and outside the core would give too small a vertex degree.
Inside these neighbourhood sets, greedily choose a fixed number of vertices in each class. Every previously chosen vertex excludes only crossing nonneighbours, so each next candidate set still has positive linear size. This produces inside . A proper -graph colouring of embeds it in that complete multipartite graph; map to . All required incident edges exist, so this embeds , a contradiction. The case simply uses enough neighbours to embed the edgeless . Hence , and the average-degree lower bound completes the answer:
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 1 16H Solution Created 2026-09-24 Updated 2026-10-05
Let be a longest path in the finite simple graph. Every neighbour of either endpoint lies on it. Among indices , consider those with edges and those with edges . Their cardinalities are the endpoint degrees, whose sum is at least , exceeding the available indices. They intersect, producing the cycleEvery connected component has at least vertices, so the graph is connected. If , an edge joins a vertex outside this cycle to it, and breaking the cycle there gives a longer path, a contradiction. Hence and this is a Hamilton cycle, proving Dirac theorem.
The complete graph is planar, has chromatic number four and a Hamilton cycle. Adding one leaf attached to one of its vertices preserves planarity and chromatic number four but prevents a Hamilton cycle, since a leaf has degree one.
For the last claim, the given plane embedding has all vertices on the outer cycle. Add noncrossing diagonals until its polygonal interior is triangulated. A triangulated polygon has a vertex incident with only its two boundary neighbours: for example the dual graph of its triangles is a tree and a leaf triangle supplies an ear. Remove this vertex. Inductively three-colour the smaller triangulated polygon, starting with a triangle. The removed vertex's neighbours are adjacent and have different colours, so it can receive the third. Restriction to the original graph givesThis uses the specified embedding, not the false assertion that every planar Hamiltonian graph is three-colourable; is already a counterexample to that broader assertion.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 110 1 Solution Created 2026-10-03 Updated 2026-10-14
Write . The Erdős-Stone theorem states that, for a fixed graph with chromatic number ,Here is the extremal number, and copies are subgraphs, not necessarily induced subgraphs. We write for the balanced complete multipartite blow-up with classes of vertices each. All asymptotic errors below concern with the forbidden graphs fixed.
The stability subgraph. We prove the high-minimum-degree multipartite stability subgraph assertion directly from the Erdős-Stone theorem. For , the edgeless spanning subgraph suffices. Suppose .
First repeatedly remove a vertex whose degree of a vertex is less than times the current order, where sufficiently slowly. The Erdős-Stone theorem gives, uniformly for every -free subgraph of order at most ,Indeed, apply the asymptotic bound at large orders; the contribution from bounded or sufficiently small orders is negligible relative to . If vertices survive, the removed edges number at mostComparing with shows that , provided dominates , the initial relative error, and . Consequently . The surviving induced subgraph satisfies and .
By the Erdős-Stone theorem, contains for some as slowly as necessary. This follows because exceeds the extremal number density for each fixed by the positive gap . Choose so slowly that and , and denote its root classes by .
An outside vertex having at least neighbours of a vertex in every determines one choice of a -subset in each . At most outside vertices can determine any fixed choice, since otherwise these vertices and the chosen root sets form . Thus at most outside vertices have this property. Exclude those vertices and the root classes; put each remaining vertex in a class for which it has fewer than neighbours of a vertex in .
Write , with . Counting missing incidences with givesSince , it follows that for every . The total missing incidences from all root vertices to assigned vertices are at most . At least of them are incidences with a vertex's own assigned root class. Hence only missing incidences go to other root classes.
Choose slowly and discard the assigned vertices with more than missing incidences to other root classes. Each remaining vertex of is adjacent to all but at most vertices of every , . If its class contained a complete bipartite graph , the vertices of this copy would have at least common neighbours of a vertex in each other root class. These sets extend the copy to , a contradiction. By the bipartite case of the Erdős-Stone theorem, the number of internal edges in each surviving class is .
The surviving graph still has edges, whereas the total possible cross-class edges, with these balanced classes, is . Thus only cross-class edges are missing. Discard the vertices missing more than cross-class edges, with slowly, and delete all internal edges. The resulting -partite subgraph has classes of size andFor the lower bound, every surviving vertex misses only vertices outside its class; the upper bound follows from the class sizes. This also records the uniform cross-class error that we need next.
Minimum degree in an extremal graph. Fix with . Choose large enough that embeds in . An extremal -free graph is therefore -free, and its edge count has the required asymptotics by the Erdős-Stone theorem. For take as above.
For any vertex , remove and introduce a new vertex whose vertex neighbourhood consists precisely of the vertices in other than . The new degree of a vertex is . This new graph remains -free. Indeed, a new copy of must use , and all its neighbours of a vertex in that copy lie in the other classes of . There are only boundedly many of them. Each misses only vertices in , so an unused vertex is adjacent to all of them. Replacing by would give in , which is impossible.
Extremality now forces , uniformly in . The upper bound for the minimum degree of a graph follows from . For , already gives . ThusThis is the minimum degree of an extremal forbidden-subgraph graph principle.
The exact extremal graph for disjoint cliques. DefineThe plus sign denotes the join of graphs. The Turán graph contains no , so every such clique in uses a vertex of . Therefore contains no vertex-disjoint such cliques, and the extremal number is at least .
Induct on , with supplied by the Turan theorem, including its equality characterization. Let and let be extremal for . The preceding results give and the -partite subgraph . Keep its classes fixed and assign each of the remaining vertices to a class in which it has fewest neighbours of a vertex in . Write the resulting classes as ; all have size . Choose a positive so slowly that dominates the outside count, every cross-class error in , and every error in the minimum degree of a graph bound.
Suppose some vertex has at least internal neighbours of a vertex. If , the assignment rule shows that has at least neighbours of a vertex in every . If , it has this many in and in the other . If contained disjoint , we could choose one vertex in each , successively avoiding those copies and the missing cross-neighbours of the already chosen vertices. This produces a further through . For , this just chooses an unused neighbour of . Hence is -free, and induction givesSince the candidate attains , equality holds throughout: is a universal vertex and is the inductively unique extremal graph. Thus is isomorphic to .
It remains to show that this case must occur. Otherwise all internal vertex degrees are less than . Together with the lower bound on and , this implies that every vertex misses only vertices outside its own class. If some contains a matching in a graph of edges, extend its edges one by one to , choosing one vertex from each other class. At every step only cross-neighbours and boundedly many used vertices are excluded. This gives disjoint forbidden cliques, a contradiction.
A maximal matching in each class therefore has at most edges, and its at most endpoints form a vertex cover of the internal edges. Their internal vertex degrees are all , so the total internal edge count is . The cross-class edge count is at most , whenceBut the balanced part sizes of the Turán graph givecontradicting extremality for . This argument also works for . Consequently, for all sufficiently large ,The uniqueness is up to isomorphic graphs, as usual for an extremal graph for disjoint cliques.
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 1 17I b Solution Created 2026-09-24 Updated 2026-10-03
The Erdős-Stone theorem states that if the chromatic number of is , thenIf is a bipartite graph with at least one edge, its chromatic number is two, so and therefore
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 3 17I Solution Created 2026-09-24 Updated 2026-10-03
A -colouring assigns one of colours to every vertex so that adjacent vertices have different colours. The chromatic number is the least such . An independent set contains no adjacent pair, and the independence number is the maximum size of such a set.
For a concrete first example, start with the five-cycle and apply the Mycielski construction times. Each application raises the chromatic number by one and preserves triangle-freeness. The resulting graph has chromatic number and contains no triangle, hence no complete graph for .
We next prove the stronger high-girth assertion by the probabilistic method. For a large integer , takeIf counts cycles of lengths , thenBy the first moment method, with probability tending to one .
Let . The expected number of independent sets of size is at mostbecause dominates . Hence with positive probability has fewer than short cycles and .
Delete one vertex from each cycle of length at most . The remaining graph has no such cycle, has at least vertices, and still has . Since each colour class is independent,This proves that there are graphs of arbitrarily high girth and chromatic number.
For the final claim, begin instead withThe expected number of triangles isso with probability tending to one . Put . The expected number of independent -sets is bounded bybecause the positive term is whereas the negative term has order .
Thus some such has fewer than triangles and no independent set of size . Delete one vertex from every triangle; more than vertices remain and the graph is triangle-free. Take any induced subgraph on exactly vertices. Vertex deletion cannot increase the independence number, so the resulting graph satisfiesThis is the triangle-free graph with sub-power independence number construction.
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 3 17G c Solution Created 2026-09-24 Updated 2026-10-03
The Erdős-Stone theorem states precisely that, for every fixed graph with chromatic number ,If the bipartite graph has an edge, then . Substitution into the theorem givesIf has no edges, then every graph of sufficiently large order contains as a subgraph, so the conclusion is immediate.
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 1 17F a Solution Created 2026-09-24 Updated 2026-09-25
A proper -coloring assigns one of colors to each vertex so adjacent vertices receive different colors. The chromatic number is the least such . Order the vertices arbitrarily and color greedily. At most colors are forbidden by previously colored neighbors, soEquality occurs for every possible maximum degree: use for , for , an odd cycle for , and for every .
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 3 17F a Solution Created 2026-09-24 Updated 2026-09-25
Colour every vertex of a graph independently and uniformly with three colours, and retain precisely the edges whose endpoints have different colours. Each edge is retained with probability , so linearity of expectation gives expected retained edge countSome colouring therefore retains at least edges. Its retained subgraph is three-colourable, and deleting edges if necessary leaves exactlyedges without increasing its chromatic number. This is the three-colourable two-thirds subgraph lemma.
To prove sharpness, take . If is three-colourable and its colour classes have sizes , then they are independent sets, sowhere the final inequality follows from Cauchy-Schwarz inequality. Since ,Given , choose with . Then every three-colourable subgraph has at most edges.
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 1 17H a Solution Created 2026-09-24 Updated 2026-09-25
Fix and sample from the Erdős-Rényi model with . Let count copies of the complete bipartite graph . By the expected subgraph count in the Erdős-Rényi model,
Put and let count independent set of size . If the chromatic number satisfies , some colour class has at least vertices, so . Moreover,because the positive part of the exponent is whereas has order . The first moment method therefore gives .
Using Markov inequality for and the union bound,for all sufficiently large . Hence at least one such contains no and has .
A triangle forces at least three vertex colours. Three suffice: colour blue; orange; and green, as in the drawing. Hence the chromatic number is three.
The five edges incident to force at least five edge colours. An explicit proper five-edge-colouring is
Give colour 5 and colour 3. At the incident colours are ; at they are ; at they are ; all are distinct. The two remaining vertices each have two distinct incident colours. Thus the edge chromatic number is five.
Perfect elimination ordering 2026-10-14
A perfect elimination ordering of a finite simple graph is a permutation of its vertices such that each set of later graph neighboursis a clique. Thus is a simplicial vertex in the remaining induced subgraph . Empty and one-vertex sets satisfy the clique condition automatically. The order here is the order of deletion: goes first.
The characterization is powerful: a finite simple graph is a chordal graph if and only if it has a perfect elimination ordering. For one proof outline, the earliest vertex of an induced cycle of length at least four would have two later graph neighbours on that graph cycle that are not adjacent, contradicting the clique condition. Conversely, every nonempty chordal graph has a simplicial vertex, and every induced subgraph of a chordal graph is a chordal graph; repeatedly deleting such a vertex supplies the ordering.[ref]
In the square-plus-diagonal chordal graph above, is a perfect elimination ordering, with later graph neighbourhoods , , , and . Starting instead with fails: its graph neighbours do not form a clique, because is absent. Thus even a chordal graph can have a poor elimination ordering.
For a larger example, join three triangles along shared edges, usingThe exact graph neighbourhoods are , , , , and . The ordering has later graph neighbourhoods , , , , and , all cliques; this certifies that the graph is a chordal graph without enumerating its graph cycles. Its maximal cliques , , form a junction tree in that order, with intersections and .
A perfect elimination ordering removes three overlapping triangles without fill-in; choosing the central vertex first adds three edges
. Details. To find an ordering, maximum cardinality search starts with all scores zero, repeatedly selects an unselected vertex of largest score, and increases each unselected graph neighbour's score by one. Reverse the selection order to obtain a candidate perfect elimination ordering. For the three-triangle graph, one valid selection sequence is , with scores at selection ; reversing it gives the displayed deletion order. On a chordal graph every tie choice works. On an arbitrary graph, test the resulting later graph neighbourhoods for the clique condition to recognize chordal graphs. Suitable adjacency lists, score buckets and a linear-time verification method give recognition.[ref]
The deletion rule also explains sparse Gaussian elimination. For a symmetric positive-definite matrix whose matrix graph is , eliminating pivot applies the Schur complement updateOnly pairs of remaining graph neighbours of can acquire new off-diagonal entries. A perfect elimination ordering already has all those edges, so Cholesky decomposition creates no symbolic fill-in. Positive definiteness ensures nonzero pivots in exact arithmetic. Special numerical cancellation can suppress predicted entries, and floating-point rounding affects their values.[ref]
Chordal Graphs and Semidefinite Optimization by Lieven Vandenberghe and others. §9.1; equation 9.2; Theorem 9.1
In the three-triangle graph, deleting first instead connects every pair in and adds exactly . The graph was already a chordal graph; the extra fill-in comes from the ordering.One further reward is optimal graph coloring. Process a perfect elimination ordering backwards and give each vertex the smallest positive color absent from its already colored graph neighbours. Those graph neighbours form a clique, so this greedy algorithm uses at most the clique number colors; any clique of that size requires at least that many. In the three-triangle graph, coloring gives colors , so both the chromatic number and the clique number are three. Every maximal clique also occurs among : take its earliest vertex and use maximality. The same ordering therefore supports graph coloring, maximal clique extraction and sparse computation.
Historically, Donald J. Rose, Robert E. Tarjan and George S. Lueker's 1976 paper connected graph elimination to symmetric sparse matrices and gave a search-based algorithm for finding a perfect elimination ordering when one exists. Its abstract distinguishes a minimal elimination ordering from a minimum one: removing avoidable fill-in does not by itself minimize the total number of added edges.[ref]
Perfect graph 2026-11-05
A perfect graph is a finite simple graph for which every induced subgraph satisfieswhere is the chromatic number and is the clique number. A clique always needs distinct colors, so perfection says this lower bound is attained throughout the induced-subgraph family. Equality for alone is not enough.
Every bipartite graph is perfect: any induced subgraph with an edge has clique number and chromatic number two, while a nonempty edgeless induced subgraph has both equal to one. The empty graph uses zero for both. A five-cycle is not perfect, because it needs three colors but has no clique larger than an edge.
The hereditary condition makes perfection useful in coloring and combinatorial optimization: deleting vertices preserves it automatically. It does not say that an arbitrary greedy vertex order will find an optimal coloring.
Proper vertex coloring Created 2026-10-14 Updated 2026-10-20
A proper vertex coloring assigns labels to the vertices of a graph so that vertices joined by an edge have different labels. Each colour class is an independent set. The chromatic number is the least number of labels needed for this form of graph coloring.
Define and for . By the Mycielskian chromatic increase and Mycielskian triangle preservation, each is a finite triangle-free graph with chromatic number . The first steps are , the Grötzsch graph, and then a 23-vertex graph needing five colours. The vertex recurrence gives . These explicit examples show how arbitrarily strong graph coloring constraints can accumulate without any three-vertex clique.
Turán density 2026-10-06
For a fixed -uniform forbidden hypergraph , its Turán density is the limit of . Averaging over smaller vertex subsets shows these normalized extremal numbers are nonincreasing, so the limit exists. For ordinary graphs, the Erdős-Stone theorem determines it from the chromatic number.
Vertex exposure for chromatic number 2026-10-07
Group random edges by their larger endpoint. These independent coordinates each change edges incident to only one vertex. Removing that vertex leaves the same graph under any two outcomes, so their chromatic numbers differ by at most one. The McDiarmid inequality with coordinate ranges of length one gives the displayed concentration bound.
