4.5 Odd graph

TL;DR: Odd graph is not cayley.

Def. Let $\Omega =\{1,2,\cdots ,2k+1\}$ and let $V={\Omega }^{\{k\}}$. Define a graph with vertex set $V$ s.t. two vertices are adjacent iff they are disjoint. This graph is called an odd graph, denoted by $O_k$.

Note that the number of vertices is $|\Omega |=\left(\genfrac{}{}{0ex}{}{2k+1}{k}\right)$, and the valency of $O_k$ is $k+1$.

For a graph $\Gamma =(V,E)$, an independent set of $V$ is the maximal set whose vertices are nonadjacent pairwise. The independence number is cardinal number of a independent set.

The independent set of $O_k$ is $\left(\genfrac{}{}{0ex}{}{2k}{k-1}\right)$. For example, $\{\{1,i_1,\cdots ,i_k\}:i_j\in \Omega \}$ is an independent set and it corresponds to a unique element $1$.

So we get a proposition:

Prop. $Aut(O_k)=S_{2k+1}$.

When $k=2$, $O_k$ is Petersen graph and so is not Cayley. In fact, every odd graph with $k\ge 2$ is not Cayley.

Thm. If $k\ge 2$, then $O_k$ is vertex-transitive, edge-transitive but not Cayley.

Proof. $O_2$ is Petersen, so it suffices to show the case of $k\ge 3$. Suppose $O_k$ is a Cayley graph of $R$. Note that $R$ is $k$-homogeneous. Assume $R$ is $k$-transitive. Consider the sequence $R>R_{{\omega }_1}>R_{{\omega }_1,{\omega }_2}>\cdots >R_{{\omega }_1,\cdots ,{\omega }_{k-1}},$we have $|R|/|R_{{\omega }_1}|=|{\omega }_1^R|=2k+1,\cdots ,|R_{{\omega }_1\cdots ,{\omega }_{k-2}}|/|R_{{\omega }_1,\cdots ,{\omega }_{k-1}}|=k+3$ and so $|R|\ge (2k+1)!/(k+2)!>\left(\genfrac{}{}{0ex}{}{2k+1}{k}\right)=|R|$ if $k\ge 3$, which is impossible. Therefore, $R$ is $k$-homogeneous but not $k$-transitive. By Kantor’s theorem, there are only finitely many group satisfying the condition. Compute orders of them and then we know all of them are impossible.