Proving distance between any two vertices is at most 2. If there are $n$ vertices and at least $\frac{1}{2}(n-1)$ degrees for each vertex, how do I prove that the distance between any two vertices is at most 2? 
I have tried drawing a few graphs with different values for $n$ but I'm not sure how to prove it for all $n$.
 A: Pick any two vertices $v_1$ and $v_2$ from the graph. If they are connected by an edge, 
their distance is $1$ and we are done. If not, there are $n-2$ vertices
for $v_1$ and $v_2$ to connect.
Let $E_1$, $E_2$ be the set of vertices connected to $v_1$ and $v_2$ respectively.
We are given
$$|E_1| \ge \frac12(n-1)\quad\text{ and }\quad |E_2| \ge \frac12(n-1)$$
This implies
$$|E_1 \cap E_2| = |E_1| + |E_2| - |E_1 \cup E_2| \ge \frac12(n-1)  + \frac12(n-1) - (n-2) > 0$$
This means $E_1 \cap E_2 \ne \emptyset$. Pick a $v$ from $E_1 \cap E_2$ and connect $v_1$ and $v_2$ by a path of length $2$ ($v_1 \to v \to v_2$). In this case, the distance between $v_1$ and $v_2$ is $2$.
A: Suppose the distance of $V_1$ and $V_2$ is larger than $2$. What would happen?


*

*As $\deg{V_1} \geq \frac12 (n-1)$, there are at least $\frac12 (n-1)$ vertices directly connected to $V_1$.

*These may not be connected to $V_2$, else we've found a path of length $2$.

*But $V_2$ has $n-1$ vertices to choose from to have an edge to. Some are not permitted. Which? Well, the $\frac12 (n-1)$ vertices from before. And $V_1$ itself. So
$$ \deg{V_2} \leq (n-1) - \frac12 (n-1) - 1 = \frac12 (n-1) - 1 < \frac12 (n-1). $$
Contradiction!

A: Let $x$ and $y$ be two non-adjacent vertices in a simple graph $G$. We show that $x$ and $y$ have a common neighbour. If $G$ is simple, then the collection of verties adjacent to $x$, call it $N(x)$, has size at least $(n-1)/2$. Similarly, $|N(y)|\geq (n-1)/2$. Also $|N(x)\cup N(y)|\leq n-2$ as $x$ and $y$ are not adjacent. But
$$
|N(x)\cap N(y)|=|N(x)|+|N(y)|-|N(x)\cup N(y)|\geq 1
$$
as desired.
