Let $G$ be a graph of order $n$. If deg $u$ $+$ deg $v$ $+$ deg $w$ $\geq n-1$ for every three pairwise nonadjacent vertices $u,v$ and $w$ of $G$, must $G$ be connected?
I know that if $H$ is a graph of order $n$ and deg $u$ $+$ deg $v$ $\geq n-1$ for every two nonadjacent vertices $u$ and $v$ of $H$, then $H$ is connected. Does this imply even further that $G$ is connected? Any help or hints would be greatly appreciated.
$\endgroup$2 Answers
$\begingroup$No. Consider the case $n=2$ with no edges. The condition is vacuously true. (Here I assume taht $u,v,w$ are silently assumed to be distinct)
$\endgroup$ $\begingroup$It is also false for other graphs too; for instance, if you choose all vertices to have degree 4 (this makes which three vertices are picked immaterial) then you can create a disconnected graph with $n=12$ vertices by picking them in two 4-regular parts as shown below:
If $u$, $v$ and $w$ are the 3 green vertices then we have $4+4+4 =12 > 11 = n - 1$.
$\endgroup$
