Ponder This Challenge - February 2002 - Undirected graph of diameter 2

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 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

Solution

• Click here to view the solution

  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

Solvers

• 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)