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?