By Turán's theorem, ex(n, Kᵣ₊₁) is achieved by the Turán graph T(n, r). For K₄ (= K_{3+1}), r = 3, so the extremal graph is T(n, 3): partition n vertices into 3 equal parts and place all edges between different parts (no edges within parts). This graph contains no K₄ because any four vertices must include two from the same part, and those have no edge between them. The balance of part sizes is essential to maximizing edges within the K₄-free constraint. K_{n/2, n/2} is T(n, 2), which avoids triangles (K₃), not K₄.
Question 2 Multiple Choice
The Kővári-Sós-Turán theorem provides an upper bound on edges in graphs forbidding the complete bipartite graph Kₛ,ₜ. What is one major application of this result outside pure graph theory?
ABounding the chromatic number of planar graphs
BProving that all Hamiltonian graphs have an Eulerian circuit
CBounding incidence counts between points and lines in combinatorial geometry
DEstablishing the four-color theorem for maps
KST has a direct application to incidence geometry: if you have n points and n lines in the plane, the number of incidences (point-on-line pairs) is equivalent to edges in a bipartite 'incidence graph' between the point set and the line set. Any such graph cannot contain K_{2,2} (no two points lie on two common lines in the Euclidean plane), so KST bounds the total incidence count. This connection — between forbidden subgraph problems and geometric configurations — illustrates how extremal graph theory provides tools for questions that do not initially look like graph problems.
Question 3 True / False
The Turán graph T(n, r) is the unique n-vertex graph with no K_{r+1} that maximizes the number of edges — any addition of a single edge creates a clique of the forbidden size.
TTrue
FFalse
Answer: True
True. Turán's theorem establishes that T(n, r) is the unique extremal graph for K_{r+1}: it is the densest K_{r+1}-free graph, uniquely determined by the balanced complete r-partite structure. Adding any edge to T(n, r) creates a K_{r+1}, because any two vertices in the same part now have an edge, and with cross-part edges they can form a larger clique. The balance of part sizes (making parts as equal as possible) is essential to the uniqueness: unbalanced partitions produce fewer edges within the K_{r+1}-free constraint.
Question 4 True / False
The Bondy-Simonovits theorem implies that most forbidden graphs H produce the same asymptotic growth rate for ex(n, H) — specifically that ex(n, H) = Θ(n²) for any choice of H.
TTrue
FFalse
Answer: False
False. The Bondy-Simonovits theorem shows that the asymptotic growth rate of ex(n, H) depends critically on the chromatic number χ(H) of the forbidden graph. For non-bipartite H (χ(H) ≥ 3), ex(n, H) = Θ(n^(1 + 1/(χ(H)−1))), which gives different exponents for different chromatic numbers. For bipartite H (χ(H) = 2), the theorem doesn't apply and the growth rate is subquadratic — often much harder to determine exactly, and frequently open. Growth rates vary substantially with the structure of H.
Question 5 Short Answer
What does the Bondy-Simonovits theorem establish about ex(n, H), and why is the bipartite case harder than the non-bipartite case?
Think about your answer, then reveal below.
Model answer: The Bondy-Simonovits theorem establishes that for any non-bipartite graph H with chromatic number χ(H), the Turán number satisfies ex(n, H) = Θ(n^(1 + 1/(χ(H)−1))). This ties extremal density directly to the coloring structure of the forbidden graph. For bipartite forbidden graphs (χ(H) = 2), this formula breaks down — the exact exponent depends on the specific structure of H in ways not captured by chromatic number alone, making many cases (including ex(n, C₆)) still open.
The deeper reason bipartite forbidden graphs are harder is that the Turán-style multipartite constructions that work for non-bipartite cases rely on chromatic structure. For bipartite H, you need algebraic constructions (often from finite geometry) or probabilistic arguments, and tighter upper bounds require more delicate combinatorial techniques. The Zarankiewicz problem — ex(n, Kₛ,ₜ) — captures much of this difficulty and remains one of the central open problems in combinatorics.