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


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


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


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

now I don't know what to do next.


2 Answers 2


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)$?

  • $\begingroup$ 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 $\endgroup$ Sep 16, 2014 at 16:33
  • $\begingroup$ 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? $\endgroup$
    – Denis
    Sep 16, 2014 at 17:24
  • $\begingroup$ their degree? what is their? the neighbors or $u$ and $v$? $\endgroup$ Sep 16, 2014 at 17:30
  • $\begingroup$ $deg(u)+deg(v)$. I detailed the hint in the answer. $\endgroup$
    – Denis
    Sep 16, 2014 at 22:01
  • $\begingroup$ 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? $\endgroup$ 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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .