Turán's theorem (1941): max edges in K_{r+1}-free graph on n vertices is ex(n,r) = (1-1/r)·n²/2 (approximately). Achieved by the complete r-partite graph T(n,r) with parts as equal as possible. ex(n,2)=⌊n²/4⌋ (Mantel 1907).
How to Use
Enter n and r:
- ex(n,r): Max edges
- Density: ex/C(n,2)
- Graph: T(n,r) structure
Turán's Theorem
Among all K_{r+1}-free graphs on n vertices, T(n,r) has the most edges. Moreover, it's the UNIQUE such graph. This is the cornerstone of extremal graph theory. The proof uses induction on n, deleting a maximum-edge vertex.
Edge Density
ex(n,r)/C(n,2) → 1-1/r as n→∞. For triangle-free: ≤1/2. For K_4-free: ≤2/3. The Erdős-Stone theorem generalizes: for any H with χ(H)=r+1, ex(n,H)/C(n,2)→1-1/r. Chromatic number determines asymptotic density!
Step-by-Step Instructions
- 1Enter n, r.
- 2Compute ex(n,r).
- 3See Turán graph.
- 4Check density.
- 5Compare to C(n,2).