Problem of the Week 896

A Special Graph

A 4-cycle, which denotes the graph below,

     *---------*
     |         |
     |         |
     |         |
     *---------*

has the following two properties:

(1) If two points are connected, they have no common neighbors.
(2) If two points are not connected, they have exactly two common neighbors.

Find a graph with more than four vertices that has these two properties.

© Copyright 1999 Stan Wagon. Reproduced with permission.