[Math] Only triangle free graph with maximal number of edges

bipartite-graphsgraph theory

In my studies of graph theory, I have recently come across the following inequality:

If $ G=(V,E) $ is a simple finite undirected triangle-free graph (it does not contain a cycle of length 3) with $ |V(G)|=n $ then we know $ |E(G)| \leq \lfloor \frac{n^2}{4} \rfloor $ with equality holding if and only if $ G=K_{\frac{n}{2},\frac{n}{2}} $ if $n$ is even or $ G=K_{\frac{n-1}{2},\frac{n+1}{2}} $ if $n$ is odd ($K_{a,b}$ denotes a complete bipartite graph with side of a vertices and side of b vertices).

I have managed to prove the inequality by induction, but the part about equality escapes me, I cannot seem to prove the only triangle free graph with specified number of edges is the complete bipartite graph given, I realize this is a theorem but I only need someone to provide help with the proof on the only triangle-free graph with given number of edges being the ones mentioned, I thank all helpers.

Best Answer

The uniqueness of the triangle-free graph $G$ with the maximal number of edges is a case of Turán's theorem. I reproduce the proof given on Wikipedia, which breaks into two parts.

Part 1: $G$ does not contain three vertices $a,b,c$ where edge $ab$ exists but edges $ac$ and $bc$ do not. Suppose on the contrary that such a triple exists. A triangle-free graph can always be constructed that has more edges:

  • If $d(c)$ is greater than both $d(a)$ and $d(b)$, delete $a$ and $b$ and replace them with two copies of $c$ that each have the same neighbours as the original $c$. The new graph remains triangle-free; $d(a)+d(b)-1$ edges are lost, but $2d(c)$ edges are gained, and the latter number is always larger.
  • Otherwise, delete $c$ and replace it with a copy of either $a$ or $b$. $d(c)$ edges are lost but $d(a)$ or $d(b)$ edges are gained, and by choosing such that the higher-degree vertex is copied we get a triangle-free graph with more edges.

The vertices of $G$ may therefore be partitioned into two sets, where two vertices are in the same set if they are not adjacent. This implies that $G$ is a complete bipartite graph.

Part 2: In such a complete bipartite graph with parts $A$ and $B$ (we assume without loss of generality that $|A|\ge|B|$), the maximum number of edges is attained if the orders of the two parts differ by at most one. If not ($|A|>|B|+1$), moving a vertex from $A$ to $B$ will cause the graph to gain $|A|-|B|-1$ edges; this last value will always be at least one.

Putting the two parts together, we have shown that the complete bipartite graphs specified in the question are the only triangle-free ones with the maximum number of edges.

Related Question