Turán's Theorem: Finding Maximum Edges in a Graph
This article explores Turán's theorem, a foundational result in extremal graph theory discovered by Pál Turán in 1941. It explains how the theorem determines the exact maximum number of edges a graph with a given number of vertices can possess without forming a complete subgraph of a specified size. By examining the construction of the Turán graph, the underlying mathematical formula, and a step-by-step example, you will learn how mathematicians calculate the structural limits of graphs.
The Core Problem: Avoiding Cliques
In graph theory, a graph is a collection of vertices (points) connected by edges (lines). A "complete subgraph," often called a clique and denoted as \(K_r\), is a subset of \(r\) vertices where every single vertex is directly connected to every other vertex in that subset. For example, \(K_3\) is a triangle of three interconnected vertices, and \(K_4\) is a group of four fully interconnected vertices.
Turán's theorem answers a specific question: Given \(n\) vertices, what is the maximum number of edges you can draw before you are mathematically forced to create a \(K_r\)?
The Solution: Partitioning the Vertices
Turán discovered that to maximize the number of edges while avoiding a \(K_r\), you must divide the vertices into separate groups and only draw edges between the groups, never within them.
The theorem achieves the maximum edge count through a specific three-step construction:
- Divide the vertices: Take the total number of vertices (\(n\)) and partition them into \(r-1\) separate groups (independent sets).
- Balance the groups: Make the sizes of these groups as equal as possible. No two groups should differ in size by more than one vertex.
- Maximize external connections: Connect every vertex in one group to every single vertex in all the other groups. Do not draw any edges between vertices that share the same group.
The resulting structure is known as a Turán graph, denoted as \(T(n, r-1)\).
Why This Method Works
The Turán graph guarantees that no \(K_r\) can exist by utilizing the Pigeonhole Principle. To form a complete subgraph of size \(r\), you need \(r\) vertices that are all connected to one another.
However, the Turán graph only has \(r-1\) groups. If you select any \(r\) vertices from the graph, at least two of them must come from the same group. Because vertices within the same group are never connected by an edge, those \(r\) vertices cannot form a complete subgraph.
Because every possible edge between different groups is already drawn, and making the groups as equal in size as possible mathematically maximizes the product of their connections, the Turán graph holds the absolute maximum number of edges possible under the restriction.
The Mathematical Formula
By counting the edges in a Turán graph, the theorem provides a clean upper bound for the maximum number of edges. For a graph with \(n\) vertices that does not contain a \(K_r\), the number of edges cannot exceed:
\[\left(1 - \frac{1}{r-1}\right) \frac{n^2}{2}\]
When the total number of vertices (\(n\)) is evenly divisible by the number of groups (\(r-1\)), this formula yields the exact maximum number of edges. If \(n\) is not evenly divisible, the exact number will be slightly less than this bound, and it is found by simply counting the edges of the constructed \(T(n, r-1)\) graph.
A Step-by-Step Example
Suppose you have a graph with \(n = 6\) vertices, and you want to find the maximum number of edges it can have without forming a \(K_4\) (where \(r = 4\)).
- Determine the number of groups: \(r - 1 = 4 - 1 = 3\) groups.
- Divide the vertices equally: Divide the 6 vertices into 3 groups. Each group gets exactly 2 vertices: \(\{A, B\}\), \(\{C, D\}\), and \(\{E, F\}\).
- Draw the edges: Connect every vertex to all
vertices outside its own group.
- Vertex \(A\) connects to \(C, D, E,\) and \(F\) (4 edges).
- In fact, each of the 6 vertices connects to the 4 vertices not in its group.
To find the total number of edges, multiply the 6 vertices by their 4 connections to get 24, then divide by 2 (since each edge connects two vertices and was counted twice). This equals 12 edges.
We can verify this using Turán's formula: \[\text{Maximum Edges} = \left(1 - \frac{1}{4-1}\right) \frac{6^2}{2} = \left(\frac{2}{3}\right) \frac{36}{2} = \left(\frac{2}{3}\right) 18 = 12\]
Therefore, 12 is the maximum number of edges. If you add a 13th edge anywhere on this 6-vertex graph, you will connect two vertices within the same group, which immediately forces the creation of a \(K_4\).