# Graph where non-adjacent vertices share a common neighbor?

Suppose $B$ is a bipartite graph on $n$ vertices with minimum degree $\delta$. It can be shown fairly easily that if $4 \delta >n$, we have the nice property that any two vertices in the same bipartition of $B$ must share at least one common neighbor.

In this question, we look at a generalization. Suppose we have an arbitrary graph $G$ on $n$ vertices. Is there a "big enough" value of $\delta$ so that any two vertices not connected by an edge must share a common neighbor (i.e. if $k\cdot \delta >n$, this property holds).

Now, what if we start putting restrictions on $G$. We know that if $G$ is bipartite, $k=4$ does in fact suffice. But what if we say $G$ is triangle free,or 5-cycle free. What can we say about $k$.

Any help would be great, tell me if I was confusing anywhere!

-
$k=4$ suffices only with the condition that the vertices are in the same bipartition, not in general. In general, the best you can say is that among two distinct vertices in a graph not joined by an edge, a sufficient condition is that the sum of their degrees must be at least n-1 for them to have a common neighbor, from which you can infer a sufficient condition on $\delta$. It is not clear if you want to characterize subclasses of graphs of diameter two or if you want to know more about the role of $\delta$ with respect to certain graph properties. – The Masked Avenger Jul 24 '13 at 18:58
Also, if the graph has diameter 2 and no cycles of length 5 or smaller, then the graph is acyclic and easily characterized. You probably want to look at diameter 2 graphs before speculating on $k$. – The Masked Avenger Jul 24 '13 at 19:13
Diameter 2 graphs are precisely the graphs with this property, no? So you're saying if the graph has this property and has girth >5, it necessarily follows the graph is acyclic (i.e. a tree)? – Anand Jul 24 '13 at 19:41
Going in another direction, star graphs have minimum degree 1 and satisfy your property. – Carl Jul 24 '13 at 21:48
I don't know if girth is defined for trees. If you look at a cycle and consider two diametrically opposite points, they must share a neighbor if the graph has diameter 2. This means these same two points are on a cycle of length less than the cycle being considered, and eventually on a cycle of length at most 5. – The Masked Avenger Jul 24 '13 at 22:11

I very much doubt such a statement is possible. As people have pointed out, your property is what is usually called "diameter equal to two". The Paley graphs are a family where the degree is $\approx \frac{n}{2}$ but they have diameter two.