In the mathematical field of graph theory, the odd graphs are a family of symmetric graphs defined from certain set systems. They include and generalize the Petersen graph.

The odd graphs have high odd girth, meaning that they contain long odd-length cycles but no short ones. However their name comes not from this property, but from the fact that each edge in the graph has an "odd man out", an element that does not participate in the two sets connected by the edge.

The odd graph ${\displaystyle O_{n}}$ has one vertex for each of the ${\displaystyle (n-1)}$-element subsets of a ${\displaystyle (2n-1)}$-element set. Two vertices are connected by an edge if and only if the corresponding subsets are disjoint. That is, ${\displaystyle O_{n}}$ is the Kneser graph ${\displaystyle KG(2n-1,n-1)}$.

${\displaystyle O_{2}}$ is a triangle, while ${\displaystyle O_{3}}$ is the familiar Petersen graph.

The generalized odd graphs are defined as distance-regular graphs with diameter ${\displaystyle n-1}$ and odd girth ${\displaystyle 2n-1}$ for some ${\displaystyle n}$. They include the odd graphs and the folded cube graphs.

Although the Petersen graph has been known since 1898, its definition as an odd graph dates to the work of Kowalewski (1917), who also studied the odd graph ${\displaystyle O_{4}}$. Odd graphs have been studied for their applications in chemical graph theory, in modeling the shifts of carbonium ions. They have also been proposed as a network topology in parallel computing.

The notation ${\displaystyle O_{n}}$ for these graphs was introduced by Norman Biggs in 1972. Biggs and Tony Gardiner explain the name of odd graphs in an unpublished manuscript from 1974: each edge of an odd graph can be assigned the unique element which is the "odd man out", i.e., not a member of either subset associated with the vertices incident to that edge.

The odd graph ${\displaystyle O_{n}}$ is regular of degree ${\displaystyle n}$. It has ${\displaystyle {\tbinom {2n-1}{n-1}}}$ vertices and ${\displaystyle n{\tbinom {2n-1}{n-1}}/2}$ edges. Therefore, the number of vertices for ${\displaystyle n=1,2,\dots }$ is