February 2002
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 ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.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
People who answered correctly:
(total or partial solutions received)
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 ponder@il.ibm.com.