5
$\begingroup$

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.

1 Answers 1

7

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.

  • 0
    haha whoops! **SPOILER ALERT:** read above answer slowly!2011-07-18