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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.