Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was browsing the library and I found Bela Bollobás book "Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics" and, on its cover, it has a graph that I don't quite recognize:

Graph from the cover

Is this graph any "interesting", as used for counterexamples (e.g., Petersen's Graph)? I could determine some of its characteristics (9 vertices, regular of valency 4, non-planar, diameter 2 etc.), but is it distinguished in any way for being featured in an important book?

share|cite|improve this question
It possesses a certain kind of regularity: If $x,y$ are neighbors, there is always $1$ path of length $2$ between them, while if they are not neighbors, there is always $2$ paths of length two between them. I forget what this sort of regularity is called, however. – Thomas Andrews Dec 20 '12 at 19:44
Ah, the term I was thinking of is "strongly regular." – Thomas Andrews Dec 20 '12 at 20:19
@ThomasAndrews, Great. Translating from your description to wikipedia's notation: for any two adjacent vertices, there is exactly 1 path of length 1 between then, which means that any 2 adjacent vertices have exactly 1 neighbor in common (in wikipedia's notation, $\lambda = 1$). For any 2 non-adjacent vertices, there is exactly 2 (vertex disjoint) paths of length 2 between them, which means that 2 non-adjacent vertices have 2 neighbors in common (in wikipedia's notation, $\mu = 2$). The graph is regular of degree $k = 4$ with $v = 9$ vertices and is, therefore, $sgr(9, 4, 1, 2)$. – rbrito Dec 21 '12 at 9:00
BTW, all of the answers are superb and I don't know what to choose as "the" answer to this question... – rbrito Dec 21 '12 at 9:06
up vote 7 down vote accepted

This graph is known as the generalized quadrangle (2,1), it is also the line graph of the $K_{3,3}$, as well as the Paley-9 graph. See here for more information. I am not aware that it is used as a prominent counterexample.

share|cite|improve this answer

It's isomorphic to the rook graph on a 3 by 3 grid:

Rook graph on a 3 by 3 grid

The Wikipedia page lists some nice properties of square rook graphs. For example, the graph is perfect, completely symmetric (i.e. looks the same from every vertex), it's the line graph of $K_{3,3}$, ...

share|cite|improve this answer

It's also the Cartesian product of a 3-cycle with another 3-cycle.

share|cite|improve this answer

It's the unit distance embedding of $K_3 \times K_3$, one of the few strongly regular graphs that has a unit distance embedding in $\mathbb{R}^2$. It is also known as $3 \times 3$ rook graph (though sometimes mistakenly as $3 \times 3$ grid graph). It also is a generalized quadrangle as pointed out above by A. Schulz.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.