There was a rather cute question last week about graphs where every pair of distinct vertices has an odd number of mutual neighbours.

The question was to show that such a graph must have an odd number of vertices, and it can be accomplished with a nice algebraic graph theory argument.

But let's up the ante a bit: can we actually characterize the graphs with this property?

Here are some examples in the family:

  • complete graphs of odd order
  • anything obtained by gluing together a bunch of odd complete graphs at a single vertex
  • a graph of the form A - B - C where A and C have the "even" version of this property (every pair of vertices have even number common neighbours) B is an odd complete graph, and A is completely joined to B, B completely joined to C.

Is this the lot?


Take a Steiner triple system on $v$ points. Let $X$ be the graph with the $v(v-1)/6$ triples as its vertices, two triples adjacent if the have exactly one point in common. We need $v\equiv1,3$ modulo 6. Then two adjacent triples have exactly $(v+3)/2$ common neighbours, and two disjoint triples have exactly 9 common neighbours. If we take $v\equiv3,7$ modulo 12 we get examples.

Of course I am just constructing strongly regular graphs with $\lambda$ and $\mu$ odd. The are strongly regular graphs with this property besides the ones listed, for example generalized quadrangles with $s$ and $t$ even. Further examples appear in Andries Brouwer's on-line tables (http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html), or Gordon Royle's (http://units.maths.uwa.edu.au/~gordon/remote/srgs/).

This suggest that a classification might be difficult.

  • $\begingroup$ Ok, I'll take that as an answer for now. Even if we were to take "doubly odd srgs" as a basic class, it's hard to see how excluding them from further consideration could help with the remainder. $\endgroup$ – Gordon Royle Mar 11 '10 at 13:20

Maybe I'm missing something, but I'm not sure that the third condition actually generates what I'll call odd graphs. For example, if I let $A$ be the graph consisting of a single vertex and $B$ be the graph consisting of two isolated vertices, then clearly both $A$ and $B$ are even. However, if I form the $A-B-C$ construction with this choice of $A$ and $B$ I get a graph with an even number of vertices, which can't be odd by the proof of the cute question.

We can fix this by further insisting that each vertex of $A$ and $C$ have odd degree. I'll call such graphs oddly even. Note that a disjoint union of two oddly even graphs is still oddly even, so it really isn't necessary to have a $A-B-C$ construction, we only need a $A-B$ construction. Furthermore, it is not necessary that $B$ is an odd clique; $B$ can in fact be any odd graph.

We thus have the following theorem.

Theorem. Let $A$ be an oddly even graph and $B$ be an odd graph. Then the graph $A-B$ formed by taking $A$ and $B$ and adding all edges between $A$ and $B$ is odd.

So, I guess the answer to the question is no.

  • $\begingroup$ Yes, I was posting in haste and missed the extra condition that the vertex degrees of the even graph must all be odd. So we can say that the complete join of an oddly even graph and an odd graph is odd, which is certainly a construction. So to complete the characterization we need - to characterize oddly even graphs - to determine the odd graphs that are NOT complete joins in this fashion. $\endgroup$ – Gordon Royle Mar 11 '10 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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