# Induction problem 7

Here's a recap of the claim:

For any positive integer n, a triangle-free graph with 2n nodes has $$\le n^2$$ edges.

### Solution

Proof by induction on n, i.e. half the number of nodes in the graph.

Base: n=1. The graph has only two nodes, so it cannot have more than one edge. Since $$n^2 = 1$$, this means the claim is true.

Inductive hypothesis: Suppose that any triangle-free graph with 2n nodes has $$\le n^2$$ edges, for $$n=1,\ldots,k$$.

Rest of inductive step: Let G be a triangle-free graph with 2(k+1) nodes ($$k \ge 1$$). Let's pick two nodes a and b that are joined by an edge. Let H be the graph we get by removing a, b, and all their edges from G. By the inductive hypothesis, H has $$\le k^2$$ edges.

Consider any other node v in G. Because G is triangle-free, v cannot be joined to both of a and b. So v has either one edge to a or b, or no edges. Therefore, since H has 2k nodes, there can be no more than 2k edges from a/b to the nodes in H. We also have one extra edge: the edge joining a to b.

The total number of edges in G is $$\le k^2 + 2k + 1 = (k+1)^2$$. This is what we needed to prove.