# Induced Clebsch subgraphs

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.

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.

The Clebsch graph can also be split in a different way into two copies of the Wagner 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.

Removing a five-vertex cycle (such as the central cycle of the Petersen graph above) leaves a copy of the Grötzsch 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:

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

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

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.

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.