Can someone give me a hint how to prove the following : Let $G$ be a simple graph with $n$ vertices, that has the property that the sum of the degrees of any two vertices, that aren't adjacent, is $n-1$. Then $G$ is connected.


Take any two vertices $v$ and $w$ which are not adjacent. There are $n-2$ other vertices in the graph. Since $deg(v)+deg(w)=n-1$, by pigeon-hole principle $v$ and $w$ have a common neighbor. So in this graph there is a path of length 2 joining any non-adjacent pairs of vertices. Thus it is connected.

  • $\begingroup$ that is not a hint! but +1 anyway... $\endgroup$ – Aryabhata Jul 18 '11 at 19:38
  • $\begingroup$ haha whoops! SPOILER ALERT: read above answer slowly! $\endgroup$ – RHP Jul 18 '11 at 19:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.