Here's a recap of the claim:
For any positive integer n, a triangle-free graph with 2n nodes has \(\le n^2\) edges.
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.