5
$\begingroup$

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:

  1. 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.
  2. 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.
  3. 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}$.
  4. 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.

  • 0
    @GerryMyerson I followed your hint. This gives a pretty straightforward (but ugly) proof by considering 4 cases: 1 degree 7 vertex where the remaining 2 vertices are connected; 1 degree 7 vertex where the 2 remaining are not connected; 2 degree 6 vertices that are connected by an edge; and 2 degree 6 vertices that are not connected directly by an edge. I was hoping for something a bit short though..2012-03-28

1 Answers 1

3

It is actually true that any graph on $2n+\delta$ nodes(where $\delta$ is $0$ or $1$) with exactly $n(n + \delta) + 1$ edges has at least $n$ triangles.

If I recollect correctly, this can be proved by induction on $n$, by showing that there is a vertex of degree $\leq n$ and then deleting it to try and apply the induction hypothesis.

  • 0
    @aelguindy: Sorry! You are welcome :-)2012-03-29