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.

Prove that a simple graph with $2n$ vertices without triangles has at most $n^2$ lines.

I've been struggling with this exercise for some time, but I can't come up with a decent proof.

share|improve this question
1  
What have you tried? Aside: It's clear you can reach $n^2$ because you can take the complete bipartite graph $K_{n,n}$. –  Thomas Andrews Feb 19 '13 at 14:08
    
@ThomasAndrews Why would you take the complete bipartite graph $K_{n,n}$ ? –  Kasper Feb 19 '13 at 14:31
    
I called it an aside because it doesn't pertain directly to your actual problem, but $K_{n,n}$ is a graph with $2n$ vertices and $n^2$ edges that does not have any triangles, so the upper bound of $n^2$ is reachable. –  Thomas Andrews Feb 19 '13 at 14:35
2  
Use whatever answer appears here: math.stackexchange.com/questions/308094/… –  Benjamin Dickman Feb 19 '13 at 15:07
add comment

3 Answers

up vote 4 down vote accepted

Hint: Show if two nodes have an edge between them, then the degrees of those two nodes must add up to at most $2n$.

If you remove those two nodes from the graph, you have a graph with $2(n-1)$ nodes and no triangles. From the first line, how many edges do you remove, at most? Proceed by induction.

share|improve this answer
    
For the first line, if you add the degree of those nods $a,b$ and it's higher then $2n$, then there must be a nod $c$ connected to both $a$ and $b$. So then there is a triangle, right ? –  Kasper Feb 19 '13 at 15:10
    
@Kasper Yes, that's the gist. –  Thomas Andrews Feb 19 '13 at 15:20
    
Suppose it is true for $n-1$, then we get $2(n-1)$ nodes and at most $(n-1)^2$ lines. If we now add 2 extra nods, then we can't add more then $1+2(n-1)$ lines to this graph. In total we get $1+2(n-1)+(n-1)^2=(1+(n-1))^2=n^2$ lines. –  Kasper Feb 19 '13 at 19:23
    
Bingo, @Kasper. Exactly. Basically, if two nodes with an edge between them have a sum of degrees less than $2n$, then removing them removes $2n-1$ nodes at most. –  Thomas Andrews Feb 19 '13 at 19:26
1  
There is a more general theorem, and Wikipedia has a non-inductive proof for it: en.wikipedia.org/wiki/Turan%27s_theorem –  Thomas Andrews Feb 19 '13 at 19:39
add comment

I answered the other question, but here is a totally different kind of argument.

Fact: If $G$ has $n$ vertices and $m$ edges, then it has an independent set of size at least $n/(D+1)$, where $D=2m/n$ is the average degree.

To see how this implies your statement, consider switching the edges and non-edges of $G$ to get the graph complement. If this has an independent set of size $3$, $G$ had a triangle. On the other hand, if $G$ has at least $n^2 + 1$ edges, then, for the complement, $D < n - 1$, so $2n/(D + 1) > 2$.

A slick proof (I've heard it attributed to Ravi Boppana) of the fact is: uniformly shuffle the vertices of $G$ and then select each vertex that appears before all of its neighbors to get a subset $I$. This $I$ is an independent set and, since each vertex $v$ is first among its $d_v$ neighbors with probability $(d_v + 1)^{-1}$, the expected size of $I$ is $$ \sum_{i\in V(G)} \frac{1}{d_i + 1} \ge \frac{n}{D+1} $$ with the inequality coming from symmetry and convexity.

share|improve this answer
add comment

See F.Harary, Graph Theory, 1969, chapt.2, "Extremal graphs"

share|improve this answer
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.