This is not a homework question, but I would appreciate if people would treat this as if it were homework. I am looking for (nonspoiler) hints.
I would like to prove that given any graph with 10 nodes and 26 edges, there must be at least 5 triangles. Here is the progress I made so far:
- I know that a graph with $n$ nodes and $\lfloor \frac{n^2}{4} \rfloor + 1$ edges must have a triangle. I am also familiar with the proof.
- I managed to find a tight case for the statement where the number of triangles is exactly 5. This is the $K_{5, 5}$ graph with one extra edge.
- I also know (and I think I can prove it) that any graph with 10 nodes and 25 edges but no triangles must be isomorphic to $K_{5, 5}$.
- A flawed proof would be to say that we start by adding the 25 edges making sure there are no triangles, then the addition of any extra edge will immediately result in 5 triangles. There's no guarantee, however, that the minimum number of triangles is obtained this way.
Any hints are appreciated.