Clebsch Graph

The Clebsch graph, also known as the Greenwood-Gleason graph (Bondy and Murty 1976, p. 242; Read and Wilson, 1998, p. 284) and illustrated above in a number of drawings, is a strongly regular quintic graph on 16 vertices and 40 edges with parameters . In fact, it is the unique strongly regular graph with these parameters (Godsil and Royle 2001, p. 230). It is also distance-regular with intersection array , as well as being distance-transitive.

It can be obtained from the 5-hypercube graph by merging antipodal vertices (i.e., those at graph distance equal to the graph diameter of 5 away), making it the 5-folded cube graph. It can also be obtained from the tesseract graph by adding edges connecting the antipodal vertices. Note that Brouwer et al. (1989, pp. 104 and 224) confusingly use the term "Clebsch graph" to refer to the 5-halved cube graph, which is strongly regular on parameters .

In addition to being isomorphic to the 5-folded cube graph, the Clebsch graph is also isomorphic to the 16-cyclotomic graph and 2-Keller graph.

The Clebsch graph is implemented in the Wolfram Language as GraphData["ClebschGraph"].

The Clebsch graph has three distinct LCF notations of order 4, six of order 2, and 21 of order 1. Bilateral LCF notation drawings are illustrated above.

If a loop is added to each vertex, the resulting adjacency matrix is equivalent to a 2-(16,6,2) block design.

The Clebsch graph is nonplanar and Hamiltonian and has chromatic number 4. The Clebsch graph is an integral graph and has graph spectrum . The bipartite double graph of the Clebsch graph is the hypercube graph .

The Clebsch graph appears to have graph crossing number 32. A straight line drawing with 32 crossings was found by Exoo (left figure above), and a bilaterally symmetric straight line drawing with 32 crossings was subsequently found by E. Weisstein (Oct. 20, 2025; right figure).

Kalbfleisch and Stanton (1968) showed that in a 3-edge coloring of the complete graph without monochromatic triangles, the subgraph induced by the edges of any one color is isomorphic to the Clebsch graph.

Xu (2026, Theorem 1.1) reports that balanced graph blow-ups of the Clebsch graph attain a sharp bound on the number of induced pentagons in terms of edge count. More precisely, if a finite simple graph has edges, then its number of induced cycle graphs satisfies

Equality is attained at the edge counts , precisely by equally sized blow-up classes, together with arbitrary isolated vertices. With vertices in each of the sixteen classes, these graphs have edges and induced pentagons.