Hosted by The Math Forum

Problem of the Week 896

A Special Graph

Fall 99 Archive || MacPOW Home || Math Forum POWs || Search MacPOW

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.

[Privacy Policy] [Terms of Use]

Home || The Math Library || Quick Reference || Search || Help 

© 1994-2008 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel School of Education.