Possible Duplicate:
Lower bound on number of edges in “triangular” graph
I am looking for a necessary condition, in terms of number of edges, in order to make any two vertices share at least neighbor in a graph. A sufficient condition is the have at least $\lceil3(n-1)/2\rceil$ edges: just glue a bunch of triangles together at one vertex. This is an example of the friendship theorem, and I want to show that it is also sufficient, as I want at least one common neighbor as opposed to a unique one.
The context of this exercise deals with set systems, in particular, distinguishable subsets. To rephrase the problem, I want to remove two vertices so that two edges become indistinguishable. In class we saw Bondy's therem, but I have trouble trying to simulate the proof.