Up
# Odd graphs

The *Odd graph* on a (2m+1)-set X, denoted by
O_{m+1} (the subscript gives the valency),
is the graph on the m-subsets of this (2m+1)-set,
where disjoint m-subsets are adjacent.
This name is due to Biggs & Gardiner, who explain the
name by *since each edge can be assigned the unique
element of X which is not a member of either vertex
incident with that edge - the "odd man out"*.

The Odd graphs are distance-regular (of diameter m),
and uniquely characterized by their intersection array.
Their automorphism group is S_{2m+1} with point
stabilizer S_{m}×S_{m+1}.

Odd graphs are Kneser graphs.
One has O_{m+1} = K(2m+1,m).

Small examples:

O_{1} is a loop on a single vertex.

O_{2} is K_{3}, the triangle.
Intersection array {2;1}.

O_{3} is the Petersen graph.
Intersection array {3,2;1,1}.

O_{4}, on 35 vertices, has intersection array {4,3,3;1,1,2}
and spectrum 4^{1} 2^{14} (-1)^{14} (-3)^{6}.
It is found as subgraph of the
Hoffman-Singleton graph,
the M_{22} graph, the
O^{-}_{6}(3) graph, and the
McL graph.
It contains the Coxeter graph.

## References

[BCN], Section 9.1D.