2

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.

Kasper
  • 13,528
  • 3
    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: http://math.stackexchange.com/questions/308094/proving-the-existence-of-triangle-by-induction – Benjamin Dickman Feb 19 '13 at 15:07
  • See F.Harary, Graph Theory, 1969, chapt.2, "Extremal graphs" – Boris Novikov Feb 19 '13 at 14:28

2 Answers2

7

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.

Thomas Andrews
  • 177,126
  • 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: https://en.wikipedia.org/wiki/Turan%27s_theorem – Thomas Andrews Feb 19 '13 at 19:39
2

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.

Louis
  • 1,083