Originally Posted by

**snowtea** Alright, think of it like this.

Start at a vertex v. Using the technique above, show that there is at least one vertex w which cannot be reached by v in 2 steps (just one is enough).

So we know that there exists v and w such that their distance is at least 3. This means all the neighbors of v and w are different.

Now draw all the neighbors of v and all the neighbors of w. Argue by the maximum degree, either v and w have distance > 3, or some pair of neighbors have distance > 3.