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.
Hint for a graph theory problem (sufficient criterion for a simple graph to be connected)
5
$\begingroup$
graph-theory
1 Answers
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.
-
0haha whoops! **SPOILER ALERT:** read above answer slowly! – 2011-07-18