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.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
2
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$ haha whoops! SPOILER ALERT: read above answer slowly! $\endgroup$ – RHP Jul 18 '11 at 19:46
