Prove a graph with degree $\ge \frac{n}{2}$ has diameter $\leq 2$

Question

$G$ is an undirected connected graph that has an even number of nodes, and every node has $≥ n/2$ degree. Prove that it has diameter $≤ 2$.

I understand that if two vertices are not connected, then each of them has at least $n/2$ edges connecting to the remaining vertices, so they must have a shared neighbor which would make the diameter $2$.

However, I don't know how to prove it formally through direct proof or contradiction, etc. since I am very new to graph theory and not familiar with all the principles and theorems.

Answer 1

If the minimal degree, denoted by $\delta(G)$, is equal to $n/2$, and the graph is connected, then every two vertices have a common neighbor (By the pigeonhole principle).

Answer 2

Let $u$ and $v$ be two distinct vertices. Then as $|\{u\}+N_G(u)| \ge \frac{n}{2}+1$ [why is that so] and $|N_G(v)| \ge \frac{n}{2}+1$ it follows that the two sets $\{u\}+N_G(u)$ and $\{v\}+N_G(v)$ intersect [make sure you see why]. As $u$ and $v$ are distinct this implies that either (i) $u \in N_G(v)$ or (ii) $v \in N_G(u)$ or (iii) $N_G(v)$ and $N_G(u)$ intersect [make sure you see why].

If either (i) or (ii) is true then the distance in $G$ between $u$ and $v$ is 1; if (iii) is true then the distance in $G$ between $u$ and $v$ is at most 2.

Thus the distance between any two distinct vertices is 2, which gives the desired result.