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!

1more comment