Prove that if $deg(u)+deg(v) \geq n-1$ for every two non adjacent vertices $u$ and $v$ of $G$ then $G$ is connected and $diam(G) \leq 2$

Let $G$ be a graph of order $n$. Prove that if $deg(u)+deg(v) \geq n-1$ for every two non adjacent vertices $u$ and $v$ of $G$ then $G$ is connected and $diam(G) \leq 2$

This is what I got so far

Let $u$ and $v$ be 2 non adjacent vertices in $G$. Since $G$ has order $n$

$$deg(u) \leq n-2$$

and

$$deg(v) \leq n-2$$

so

$$deg(u) +deg(v) \leq 2(n-1)$$

thus

$$n-1 \leq deg(u)+deg(v) \leq 2(n-1)$$

now I don't know what to do next.

Hint: prove that $u$ and $v$ have a common neighbour.

Detailed hint: Assume $u$ and $v$ have no common neighbour. Let $N(x)$ be the set of neighbours of $x$. Then $|N(u)\cup N(v)|=deg(u)+deg(v)$. But what is the maximal $N(u)\cup N(v)$?

• can you explain it a little bit further please? I still don't know how to prove that $u$ and $v$ have a common adjacent vertex Sep 16, 2014 at 16:33
• if not, then their neighbours partition a subset of $G\setminus\{u,v\}$. How big can the sum of their degrees be in this case? Sep 16, 2014 at 17:24
• their degree? what is their? the neighbors or $u$ and $v$? Sep 16, 2014 at 17:30
• $deg(u)+deg(v)$. I detailed the hint in the answer. Sep 16, 2014 at 22:01
• ok, so if they don't have any common neighbor then $deg (u) \leq n-2-deg(v)$ so $deg(u)+deg(v) <n-1$ which is a contradiction, so they must have some common neighbor. Am I correct? Sep 16, 2014 at 22:13

Let $$u$$ and $$v$$ be non-adjacent vertices of $$G$$. Assume that $$N(u) \cup N(v) = \emptyset$$. Then $$deg(u)+deg(v) \leqslant n-2$$. Contradiction with $$deg(u)+deg(v) \geqslant n-1$$. Hence $$N(u) \cup N(v) \neq \emptyset$$. Thus $$d_G(u,v) \leqslant 2$$ for all $$u$$ and $$v$$ of $$G$$ and finnaly $$\textrm{diam}(G) \leqslant 2$$.