Pick a pair of vertices and , we have to prove that the distance between them is at most 2.

If and were adjacent, we are done, their distance is not greater than 2.

We consider now the case in which and are not adjacent.

Suppose the statement were false, that is, each of the neighbours of is not a neighbour of .

Since we have acontradictionsince !

The -2 comes from the fact that can't be a neighbour of itself or .

Note that we didn't use the hypothesis that G was connected, but we needed to be a simple graph .