IBM Ponder This #046 · 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.

Solution

Best opened after a real attempt

To be added.