# Section4.1Distance Regularity

First some code to allow us to test if a graph is distance regular. The main use of this is to provide a test that some graph we have constructed is distance regular.

If $X$ is distance-regular, then the distance partition is equitable and the quotient matrix with respect to this partition is the same for all vertices.

We use the Kneser graphs as a test case, though we must relabel the vertices to convert them from sets to integers.

If the partition is not equitable, the response would be a simple False.

There is a built-in command in sage is_distance-regular() which we would normally use in place of the above, but we wanted to demonstrate the use of is_equitable(). We will use the built-in command in the next section.

Many distance-regular graphs are distance-transitive. We can test for this by verifying that our graph is vertex transitive and the number of orbits of the stabilizer of a vertex is the diameter plus one.

The Kneser graph has a perfect 1-code—a set of seven vertices pairwise at distance three. If we delete the vertices in a perfect 1-code, the resulting graph is the Coxeter graph which is a distance-regular cubic graph. It is not too hard to see that a perfect 1-code will be a coclique of size seven that is maximal under inclusion. So we can find one and construct the Coxeter graph as follows.

We confirm that $Y$ has girth seven, an increase of one from the girth of $X$. You might verify that $Y$ is distance-transitive.