IBM Research | Ponder This | February 2002 challenges

# Ponder This

## February 2002

<<January February March>>

Ponder This Challenge:

This puzzle is suggested by Alan Hoffman:

An undirected graph G has no multiple edges, no triangles, and no quadrilaterals. It has diameter 2, and does not have constant degree. One particular node has degree 7. How many nodes are there? Prove it.

(Aside: if we replace the condition "does not have constant degree" with the condition "does have constant degree d", it is known that the graph must be either a pentagon (d=2), the Petersen graph (d=3), the Hoffman-Singleton graph (d=7), or possibly a graph with 3250 nodes (d=57) whose existence is uncertain; no others are possible.)

Definitions of terms:

G is a set of nodes and a set of edges; each edge (x,y) joins two different nodes x and y, without regard to order.
"No multiple edges": vertices x,y are joined by at most one edge.
"No triangles" outlaws three nodes x,y,z such that (x,y), (y,z), and (z,x) are all edges.
"No quadrilaterals" outlaws four nodes x,y,z,w such that (x,y), (y,z), (z,w) and (w,x) are all edges.
"Diameter 2" means that for any two different nodes x,y, there is either a path of length 1 (an edge (x,y)) or a path of length 2 (a node z and edges (x,z) and (z,y)) joining them; and at least one pair requires a path of length exactly 2.
The "degree" of a node is the number of edges hitting it.
"Not constant degree" means that not all nodes have the same degree.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the webmaster.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: webmster@us.ibm.com

Challenge: 02/01/2002 @ 9:30 AM EST
Solution: 02/28/2002 @ 3:00 PM EST
List Updated: 02/28/2002 @ 2:00 PM EST

Chu-Wee Lim (2.5.2002 @ 9:50 AM EDT)
Ionel Santa (2.5.2002 @ 9:54 AM EDT)
Oleg Mazurov (2.5.2002 @ 10:15 AM EDT)
Joseph Devincentis (2.5.2002 @ 11:15 AM EDT)
Sarang Aravamuthan (2.6.2002 @ 1:15PM EDT)
Jose H. Nieto (2.6.2002 @ 1:15 PM EDT)
Vadim Alexandrov (2.6.2002 @ 2:45 PM EDT)
Vince Lynch (2.7.2002 @ 11:45 AM EDT)
Sriram Ramabhadran (2.7.2002 @ 11:45 AM EDT)
Graeme_McRae (2.7.2002 @ 11:45 AM EDT)
Sameer Udeshi (2.7.2002 @ 11:45 AM EDT)
Jacques Willekens (2.7.2002 @ 11:45 AM EDT)
John G. Fletcher (2.11.2002 @ 10:45 AM EDT)
Shmuel Spiegel (2.12.2002 @ 12:00 PM EDT)
Thierry Eric (2.19.2002 @ 11:00 AM EDT)
Ed Sheppard (2.19.2002 @ 11:00 AM EDT)
Mihai Cioc (2.25.2002 @ 1:00 PM EDT)
Prashanth Hande (2.26.2002 @ 10:00 AM EDT)
Andrew Byde (2.26.2002 @ 10:00 AM EDT)
Mohammad Ebrahem Aharpour (2.28.2002 @ 11:00 AM EDT)
Shankar Ram L (2.28.2002 @ 11:00 AM EDT)
Por Julio Subocz (2.28.2002 @ 2:00 PM EDT)

Attention: If your name is posted here and you wish it removed please send email to the webmaster.