There was a rather [cute question last week](https://mathoverflow.net/questions/17269/let-g-be-a-graph-such-that-for-all-u-v-v-g-u-no-equal-to-v-n-u-n-v) 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?



Graphs where every two vertices have odd number of mutual neighbours
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.


