Induction problem 7


Each time n increases, you add two vertices. So your inductive step should remove two vertices a and b, and all edges ending at them.

You'll use the inductive hypothesis on the rest of the graph, then try to count the extra edges that involve a and/or b.

When you remove a pair of vertices, you can choose which pair of vertices to remove. In particular, you can decide to pick a pair that is joined by an edge. Or you could pick a pair that isn't joined by an edge. Which of the two options gives you the best control over the other edges involving a and b?

Does your inductive step have two cases, depending on whether a and b are joined by an edge? Very tempting approach, but don't do that. Commit to one of the two options.

Have you used the fact that the graph is triangle-free?