What happens to ex(n, K_r) — the maximum number of edges in a K_r-free graph on n vertices — as r increases while n stays fixed?
AIt decreases, because larger cliques are harder to avoid and require a sparser graph
BIt increases, because forbidding a larger clique is a weaker constraint, allowing more edges
CIt stays the same, because the number of vertices has not changed
DIt approaches zero, since avoiding any clique eventually forces an empty graph
Forbidding K_r is a weaker constraint when r is large — you only need to avoid r-cliques, not smaller ones. The Turán edge count (1 − 1/(r−1)) · n²/2 increases toward n²/2 as r grows. Triangle-free graphs (r=3) are the most restricted at roughly n²/4; as r grows, the bound approaches n²/2. Larger forbidden clique means more edges are permitted.
Question 2 Multiple Choice
A student claims: 'K_{3,3} is the densest triangle-free graph on 6 vertices.' What does Turán's theorem say about this claim?
AFalse — K_{3,3} contains triangles and is not triangle-free
BTrue — T(6, 2) is exactly K_{3,3}, splitting 6 vertices into two equal parts, achieving the maximum edge count for K₃-free graphs on 6 vertices
CFalse — a denser triangle-free graph on 6 vertices can be constructed using unequal partition sizes
DTrue — but any bipartite graph on 6 vertices achieves this same maximum
T(6, 2) is the Turán graph for K₃-free graphs with n=6: partition into r−1 = 2 equal parts of size 3 each and add all edges between parts. This gives K_{3,3} with 9 edges. It is triangle-free (a triangle would need an edge within a part, which doesn't exist). Turán's theorem guarantees no other triangle-free graph on 6 vertices can exceed 9 edges, and the balanced partition is uniquely optimal.
Question 3 True / False
According to Turán's theorem, a K₄-free graph on n vertices can have approximately n²/3 edges, compared to roughly n²/4 for a K₃-free graph — meaning forbidding a larger clique allows more edges.
TTrue
FFalse
Answer: True
The Turán edge count formula (1 − 1/(r−1)) · n²/2 gives n²/4 for r=3 (K₃-free) and n²/3 for r=4 (K₄-free). Avoiding K₄ is a weaker constraint than avoiding K₃, so a denser graph is achievable. As r grows, the bound approaches n²/2, the complete graph.
Question 4 True / False
In the Turán graph T(n, r−1), making one partition class much larger than the others while keeping remaining parts equal would increase the total number of edges beyond the balanced construction.
TTrue
FFalse
Answer: False
Any imbalance decreases the edge count. If two parts have sizes a and b with a > b+1, moving a vertex from the larger to the smaller replaces a·b inter-part edges between those classes with (a−1)·(b+1) = a·b + a − b − 1, which is larger when a > b+1. Equal parts maximize the product of partition sizes and thus maximize edges. Unbalanced partitions waste edge potential.
Question 5 Short Answer
Why does the Turán graph T(n, r−1) contain no K_r, and why does balancing the partition sizes maximize edges?
Think about your answer, then reveal below.
Model answer: T(n, r−1) has r−1 independent sets (parts) with edges only between different parts. Any r chosen vertices must include two from the same part by the pigeonhole principle, but there are no edges within parts — so no K_r can exist. Balancing matters because any imbalance can be corrected: moving a vertex from a larger part (size a) to a smaller part (size b, with a > b+1) increases inter-part edges between those two classes from a·b to (a−1)(b+1), which is strictly larger. Equal parts maximize the sum of products of partition sizes, yielding the most edges possible.
These two facts together give the full picture: the construction is K_r-free by pigeonhole, and it is optimal because the balanced partition maximizes edges. The Zykov symmetrization argument formalizes why any asymmetry can always be profitably corrected.