February 2002
First let's notice that between any two different nodes s,t, there is exactly one path of length 1 or 2. (We are ignoring longer paths.) Indeed, the "diameter 2" condition implies at least one such path, and if there were two such paths we would have a forbidden configuration: either a multiple edge (if both paths are of length 1), a quadrilateral (both of length 2), or a triangle (of lengths 1 and 2).
Next we show that if nodes x and y are not connected by an edge, then x and y have the same degree. So assume x,y are not connected by an edge. Count the number of paths from x to y of length either 2 or 3, where we allow backtracking.
Each neighbor s of x accounts for exactly one such path, since there is exactly one path of length 1 or 2 from s to y, and a path from x to y of length 2 or 3 begins with an edge to some neighbor s and continues with a path of length 1 or 2 from s to y.(s is unequal to y because (x,y) is not an edge.) So the number of such paths is equal to the degree of x. But it is also equal to the degree of y, by the same reasoning.
Turning it around, if x and y have different degrees, then they are connected by an edge.
Suppose x,y,z all had different degrees. Then they would be pairwise connected by edges, forming a triangle. So there are exactly two different degrees, say d1 and d2.
All nodes of degree d1 are connected to all those of degree d2. Further, if both x and z have degree d1, and w and y have degree d2, then (x,y,z,w) forms a quadrilateral, which is outlawed. So there is only one node of degree d1 (call it x),and x is connected to all other nodes. If some two nodes of degree d2 are connected,they (along with node x) form a triangle, which is outlawed. So the nodes of degree d2 are connected only to node x.
Conclusion: the graph is a "claw" or "star" K1,n: one node of degree n, connected to n nodes of degree 1. Since n=7, the number of nodes is 8.
(The first part of the proof can be abbreviated by mathematical notation: the adjacency matrix A commutes with B=A2+A, and we see that B is of the form J+D where J is the matrix of all ones and D is a diagonal matrix.)
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com