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.

Comments

What happens if G doesn't contain any edges? That's going to make it difficult to find a suitable a and b to remove. If your proof also has this mistake, take a moment to patch it before looking at the final solution.