Characterization of Laborde-Mulder graphs (extended odd graphs) (Q1916118)

A graph is \((0, 2)\) if any two vertices have either 0 or 2 neighbors in common. The Laborde-Mulder graph \(E_k\) consists of all subsets of a \(2k- 1\)-element set of cardinality at most \(k- 1\), with an edge between such when they differ by either exactly 1 or \(2k- 2\) elements. This paper proves that any \((0, 2)\)-graph of degree \(d\) on \(2^{d- 1}\) vertices has diameter at least \(\lfloor d/2\rfloor\), with equality for odd \(d\) iff it is a Laborde-Mulder graph.