Let $G$ be a graph of order $n\geq 2$ such that $\delta(G) \geq \frac{1}{2}(n-1).$ Show any two non-adjacent vertices in $G$ have a common neighbour.
May I know if my proof is correct? Thank you.
Let $n$ be even. Suppose there exists non-adjacent $u,v$ such that both have no common neighbour. Since $\text{deg}(u) \ge\frac{1}{2}n,$ there exists at least $\frac{1}{2}n$ vertices incident to $u$. Similarly, there exists at least $\frac{1}{2}n$ vertices incident to $v.$ None of the vertices incident to $u$ is incident to $v$ and none of the vertices incident to $v$ is incident to $u.$
Hence total number of vertices $\geq \frac{1}{2}n + \frac{1}{2}n+2 > n.$ (Contradiction).
The case of $n$ is odd is similar.
Best Answer
Your proof is correct but you do not need to separate out the odd and even cases:- Suppose the result is false for the two non-adjacent vertices $u$ and $v$. Then there are at least $\delta(G)$ vertices adjacent to $u$ and $\delta(G)$ vertices adjacent to $v$. Together with $u$ and $v$ this means that $G$ has at least $2+2\delta(G)$ vertices and then we obtain the contradiction $$\delta(G)\le\frac{n-2}{2}.$$