Today I've been playing with the induced subgraphs of the Clebsch graph. Several other interesting and well-known graphs can be obtained from it by deleting a small number of vertices and forming the induced subgraph of the remaining vertices.

To begin with, one simple construction of the Clebsch graph is to take all length-four binary strings as vertices, and to make two strings neighbors when they differ either by a single bit or by all four bits. So it has sixteen vertices and 40 edges, and can be visualized as a four-dimensional hypercube with the long diagonals added.

The Clebsch graph as a four-dimensional hypercube with the long diagonals added

It can be split into two three-dimensional cubes, by partitioning the binary strings according to the value of their first bit. Since the cube is bipartite, we can color the whole Clebsch graph with four colors, by using two colors within each cube. This is optimal, because the largest independent sets in the Clebsch graph (the sets of neighbors of a single vertex) have five vertices, not enough for three of them to cover the whole graph.

Two cubes in the Clebsch graph

The Clebsch graph can also be split in a different way into two copies of the Wagner graph:

Two Wagner graphs in the Clebsch graph

Removing a vertex and its five neighbors from the Clebsch graph (a \( K_{1,5} \) subgraph) leaves a copy of the Petersen graph as the remaining graph. Similarly removing a maximum independent set leaves a Petersen graph together with a single isolated vertex.

Petersen subgraph of the Clebsch graph

Removing a five-vertex cycle (such as the central cycle of the Petersen graph above) leaves a copy of the Grötzsch graph:

Grötzsch graph as subgraph of the Clebsch graph

Removing a four-vertex maximal independent set (four independent vertices that do not have a single common neighbor) leaves a subdivision of the complete bipartite graph \( K_{4,4} \), in which four edges forming a matching have been subdivided:

Subdivision of K_{4,4} in the Clebsch graph

Removing a four-cycle leaves a twelve-vertex torus graph with 24-way symmetry:

Symmetric 12-vertex torus graph in the Clebsch graph

Here are a couple of less-symmetric large planar induced subgraphs.

One of two large planar induced subgraphs of the Clebsch graph

One of two large planar induced subgraphs of the Clebsch graph

The second of these planar graphs can be formed by removing all binary strings with equal numbers of zeros and nonzeros, a six-vertex subset that induces a three-edge matching. If we instead partition the vertices into strings with even and odd parity, we get a partition of the Clebsch graph into two eight-vertex induced matchings.

Partition of the Clebsch graph into two induced matchings

The Schläfli graph (or its complement) has many induced Clebsch graphs inside it, so presumably it also has an interesting collection of symmetric induced subgraphs. But that's getting a bit too large for the sort of by-hand analysis I did to get the list here; it calls for automation instead.