1
$\begingroup$

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.

  • 0
    This is obvious... but you're saying the diameter is $\leq 2$. So, perhaps there is a condition on number of edges and diameter.2012-02-13
  • 0
    Related: http://math.stackexchange.com/questions/107876/lower-bound-on-number-of-edges-in-triangular-graph.2012-02-13
  • 0
    @Graphth thanks for your reply. Yes diameter $\le2$ is necessary, however not sufficient. Consider a star, which has $n-1$ edges, and the center does not share any neighbor with other vertices...2012-02-13
  • 0
    @Aryabhata Thanks! That's exactly what I needed... and it was asked 2 days ago......2012-02-13
  • 0
    Voting to close as dupe then.2012-02-13

0 Answers 0