Graphs where every two vertices have odd number of mutual neighbours

Question

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?

Answer 1

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.

Answer 2

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.