Clebsch graph

The 40-edge variant is the dimension-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of Robert E. Greenwood and Andrew M. Gleason (1955), who used it to evaluate the Ramsey number R(3,3,3) = 17.

(In an n-dimensional hypercube, a pair of vertices are opposite if the shortest path between them has n edges.)

Alternatively, it can be formed from a 5-dimensional hypercube graph by identifying together (or contracting) every opposite pair of vertices.

Another construction, leading to the same graph, is to create a vertex for each element of the finite field GF(16), and connect two vertices by an edge whenever the difference between the corresponding two field elements is a perfect cube.

It produces two subsets of 16 vertices that are disconnected from each other; both of these half-squares of the hypercube are isomorphic to the 10-regular Clebsch graph.

Two copies of the 5-regular Clebsch graph can be produced in the same way from a 5-dimensional hypercube, by connecting pairs of vertices whose Hamming distance is exactly four.

Because the Clebsch graph is a triangle-free graph, this shows that there is a triangle-free three-coloring of the edges of K16; that is, that the Ramsey number R(3,3,3) describing the minimum number of vertices in a complete graph without a triangle-free three-coloring is at least 17.

The 5-regular Clebsch graph can be embedded as a regular map in the orientable manifold of genus 5, forming pentagonal faces; and in the non-orientable surface of genus 6, forming tetragonal faces.

Because this polynomial can be completely factored into linear terms with integer coefficients, the Clebsch graph is an integral graph: its spectrum consists entirely of integers.

It is also connected-homogeneous, meaning that every isomorphism between two connected induced subgraphs can be extended to an automorphism of the whole graph.

K 16 3-coloured as three Clebsch graphs.