# Hint for a graph theory problem (sufficient criterion for a simple graph to be connected)

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 Answer

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.

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