If $G$ is a graph of order $n\geq 2$ such that $\delta(G) \geq \frac{1}{2}(n-1),$ then any two non-adjacent vertices in $G$ have a common neighbour.

Question

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.

Answer 1

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}.$$

Answer 2

You statement is not correct.

Take a graph $V=\{1,2,3\}$ and $E=\{12,23\}$.

Then $n= 3$ and $\delta(G) = 1\geq {1\over 2}(3-1)$.

But $1$ and $2$ does not have a common neighbour.

---

An edit after OP's edit

Yes it is OK. You can write it like this, no need to separate two cases for $n$:

Suppose that we have two points $A$ and $B$ which are not adjacent. And let $M$ and $N$ be the sets of the neighbors of $A$ respectively $B$. Then since $A$ and $B$ are not adjacent we have $A\notin N$ and $B\notin M$. Suppose they don't have common neighbor, so $M\cap N =\emptyset $. Now by PIE we have $$n-2\geq|M\cup N|=|M|+|N|-|M\cap N| \geq 2{n-1\over 2}$$ A contradiction.