Odd graph

Definition

Let $n$ be a natural number greater than or equal to 2.

The odd graph with parameter $n$, denoted $O_{n}$, is defined as the Kneser graph $KG_{2n-1,n-1}$. Explicitly, dix a set of size $2n-1$ (we usually take the set as $\{1,2,\dots ,2n-1\}$ for convenience). Then:

1. The vertex set of $O_{n}$ is the collection of $(n-1)$-element subsets of the fixed set of size $2n-1$.
2. The edge set of $O_{n}$ is defined as follows: two vertices of $O_{n}$ are adjacent if and only if they are disjoint when viewed as subsets of the $(2n-1)$-element set.

Particular cases

Value of $n$	Odd graph $O_{n}$
2	triangle graph
3	Petersen graph
4	odd graph:O4

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	${\binom {2n-1}{n-1}}={\frac {(2n-1)!}{(n-1)!n!}}$	By definition, it is the number of $(n-1)$-element subsets of a fixed $(2n-1)$-element set.
size of edge set	${\frac {1}{2}}{\binom {2n-1}{n-1,n-1,1}}={\frac {1}{2}}{\frac {(2n-1)!}{(n-1)!(n-1)!}}$	This is the number of ways of picking two disjoint and interchangeable $(n-1)$-element subsets from a $(2n-1)$-element set.

Numerical invariants associated with vertices

Since the graph is a vertex-transitive graph, any numerical invariant associated to a vertex must be equal on all vertices of the graph. Below are listed some of these invariants:

Function	Value	Explanation
degree of a vertex	$n$	For any subset of size $n-1$, we need to count all the subsets of size $n-1$ that are disjoint from it. This is ${\binom {(2n-1)-(n-1)}{n-1}}={\binom {n}{n-1}}=n$.
eccentricity of a vertex	$n-1$	Fill this in later

Other numerical invariants

Function	Value	Explanation
clique number	3 for $n=2$ 2 for $n\geq 3$
independence number	Fill this in later
chromatic number	Fill this in later
radius of a graph	$n-1$	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	$n-1$	Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
odd girth	$2n-1$
even girth	6 for $n\geq 3$ $\infty$ for $n=2$
girth of a graph	$\min\{2n-1,6\}$. Explicitly, it is $2n-1$ for $n=2,3$ and 6 for $n\geq 4$.