# 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. $$n^2 = 1$$ The graph has only two nodes, so it cannot have more than one edge. Since $$n^2 = 1$$, this menas 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$$). There are two cases:

Case 1: G has no edges. Since ($$k \ge 1$$), this means that G has $$\le (k+1)^2$$ edges, which is what we needed to prove.

Case 2: G has at least one edge. 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 a node v in H (i.e. a node that's not a or b). 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 the number in H, plus the nodes from a/b to a node in H, plus the edge joining a to b. That total is $$\le k^2 + 2k + 1 = (k+1)^2$$. This is what we needed to prove.