# Induction problem 7

### Hints

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?