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.

Two vertices are connected by an edge if and only if the corresponding subsets are disjoint.

[2][5] Odd graphs have been studied for their applications in chemical graph theory, in modeling the shifts of carbonium ions.

[6][7] They have also been proposed as a network topology in parallel computing.

for these graphs was introduced by Norman Biggs in 1972.

[9] 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.

correspond to sets that differ from each other by the removal of

steps, each pair of which performs a single addition and removal.

[13] However, despite their high degree of symmetry, the odd graphs

[14] Because odd graphs are regular and edge-transitive, their vertex connectivity equals their degree,

have girth six; however, although they are not bipartite graphs, their odd cycles are much longer.

be an odd graph defined from the subsets of a

, they are not disjoint, and form an independent set of

different independent sets of size

It follows from the Erdős–Ko–Rado theorem that these are the maximum independent sets of

Further, every maximum independent set must have this form, so

This complementary set induces a matching in

Each vertex of the independent set is adjacent to

[2] Because of this decomposition, and because odd graphs are not bipartite, they have chromatic number three: the vertices of the maximum independent set can be assigned a single color, and two more colors suffice to color the complementary matching.

By Vizing's theorem, the number of colors needed to color the edges of the odd graph

is a power of two, the number of vertices in the graph is odd, from which it again follows that the number of edge colors is

[2][16] Biggs[9] explains this problem with the following story: eleven soccer players in the fictional town of Croam wish to form up pairs of five-man teams (with an odd man out to serve as referee) in all 1386 possible ways, and they wish to schedule the games between each pair in such a way that the six games for each team are played on six different days of the week, with Sundays off for all teams.

In this story, each game represents an edge of

provides a solution to the players' scheduling problem.

[17] As the odd graphs are vertex-transitive, they are thus one of the special cases with a known positive answer to Lovász' conjecture on Hamiltonian cycles in vertex-transitive graphs.

Biggs[2] conjectured more generally that the edges of

is odd, the leftover edges must then form a perfect matching.

prevents an 8-color edge coloring from existing, but does not rule out the possibility of a partition into four Hamiltonian cycles.