Let $G$ be a graph of order $n$ with the property that if the degrees of two vertices $u$ and $v$ sum to less that $(n-1)$, then $u$ and $v$ are adjacent. Prove that $G$ is connected.

Can someone help me with this problem? I don't understand how knowing the sum of the two vertices degrees aids in proving connectivity.

  • $\begingroup$ Something is wrong with the question. Do you mean the degree sum between two vertices should be at least $n-1$? $\endgroup$ – Batominovski May 1 '17 at 21:28
  • 1
    $\begingroup$ Suppose you could decompose $G$ into two nonempty parts of size $k$, $n-k$ with no edges between the two parts. Choose $u$ in the first part, $v$ in the second part. Then $\deg(u) \le k-1$ and $\deg(v) \le n-k-1$ so $\deg(u) + \deg(v) < n-1$, but $u$ and $v$ are not adjacent, which contradicts the assumption. $\endgroup$ – Daniel Schepler May 1 '17 at 21:33
  • $\begingroup$ I guess it was meant not less. $\endgroup$ – Smylic May 1 '17 at 21:37
  • $\begingroup$ No, the question I was given was exactly that. The hint I was given was a case by case basis, where 1) uv is an edge and 2) uv is not an edge and then from there the answer could be derived but even will small order of n, I keep getting confused $\endgroup$ – D_inquisitive May 1 '17 at 22:06
  • $\begingroup$ Fix any pair of distinct nodes u,v. By assumption, either they are adjacent, or the sum of their degrees is at least n-1. In the latter case, they have at least one common neighbor. Therefore, in both cases, there is a path connecting u,v. $\endgroup$ – Evangelos Bampas May 2 '17 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.