Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
You might be able to do it by arguing that there must be a vertex of degree at least 7, or at least two vertices of degree at least 6, and showing that there have to be some edges connecting vertices connected to the high degree vertices, thus forming triangles. –  Gerry Myerson Mar 28 '12 at 11:58
    
@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.. –  aelguindy Mar 28 '12 at 15:17
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
It was more of a solution than a hint :-) but it works. Thanks! –  aelguindy Mar 29 '12 at 8:05
    
@aelguindy: Sorry! You are welcome :-) –  Aryabhata Mar 29 '12 at 22:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.