Prove that Odd graph has girth of 6

Question

I'm stuck in a problem and need help figuring it out.

1.1.28. $(+)$ The Odd Graph $O_{k}$. The vertices of the graph $O_{k}$ are the $k$-element subsets of $\{1,2, \ldots, 2 k+1\} .$ Two vertices are adjacent if and only if they are disjoint sets. Thus $O_{2}$ is the Petersen graph. Prove that the girth of $O_{k}$ is 6 if $k \geq 3$

source : West, Introduction to Graph Theory

My solution :

Let [2k+1] denote the set {1, 2, 3, ... 2k+1}

Clearly girth cannot be 1 or 2.

Also girth cannot be 3, unless k = 1, as, for girth = 3, we need 3 disjoint k-element subset of [2k+1]. Say x, y, z. Then $|(x \bigcup y \bigcup z)| \le 2k+1, i.e. 3k \le 2k+1, i.e. k\le1$.

Girth cannot be equal to 4, as, consider any two non-adjacent vertices x, y. We prove that they have exactly one common neighbour. Say, z. Clearly , $k-1\ge|x \bigcap y|\ge1,$ as x and y should have some common element(s), also, $|x\bigcap z| = |y\bigcap z| = |x\bigcap y\bigcap z| = 0.$ Now, $|x\bigcup y\bigcup z|\le2k+1.$ i.e, expanding using set principles we get, $k-1\le|x \bigcap y|.$ Thus, $k-1=|x \bigcap y|$ .i.e. x and y differ only in single element. And $|(x\bigcup y)|=k+1$, using set principles. Clearly, z should be k-element subset from the set $[2k+1]-(x\bigcup y)$, the size of which is k. So, z is uniquely determined, and no other set full-filling these criteria exists, Therefore, girth of 4 is impossible.

I'm unable to proceed further to show the non-existence of girth of 5, for $k\ge3$. Please help to proceed further.

Answer 1

@araomis's answer addresses your most direct question, the fact that $O_k$ contains no cycles of length $5$ when $k \geq 3$. However, you still need to show that there is a cycle of length $6$ in $O_k$. For the sake of completeness, I'll write a full proof here:

As you mentioned, it's completely obvious that the girth of $O_k$ isn't $3$ (you can't have $3$ disjoint $k$-subsets of a set of size $2k + 1$ (when $k \neq 1$)).

You also noticed that vertices with a common neighbor in $O_k$ correspond to $k$-subsets with exactly $k - 1$ elements in common. Hence that common neighbor between any two vertices is unique, rendering a $4$-cycle in $O_k$ impossible. Hence $O_k$ doesn't have girth $4$, either.

I'll prove that $O_k$ doesn't have girth $5$ (when $k \geq 3$; this hypothesis is important in this case) in a somewhat different way than araomis -- you'll have to put in some work yourself (or just read their answer). Two vertices in $O_k$ at distance $2$ from a single vertex have at least $k - 2$ common neighbors (why? the argument will resemble what you wrote in your own question when tackling the girth $\neq 4$ case). Since $k \geq 3$, such vertices cannot be adjacent (again, why?) and hence $O_k$ doesn't have a cycle of length $5$ (when $k \geq 3$).

Finally, we demonstrate that $O_k$ contains a cycle of length $6$ (and, combined with the results of the previous 3 paragraphs, this will show that the girth of $O_k$ is equal to $6$). Set $$A = \{2, ..., k\}$$ and $$B = \{k+2, ..., 2k\}.$$ Then $(A \cup \{1\}, B \cup \{k+1\}, A \cup \{2k+1\}, B \cup \{1\}, A \cup \{k+1\}, B \cup \{2k+1\})$ forms a cycle of length $6$ in $O_k$ (verify this). This completes the proof.

Answer 2

I think this works:

Notice that you have already shown that if $x$ and $y$ are non-adjacent but have a common neighbour, then $x$ and $y$ differ in exactly one element. In other words, $x$ and $y$ share $k - 1$ elements.

Now assume for a contradiction that there exists a cycle of length $5$. Let $x$ and $y$ be non-adjacent on this cycle and let $z$ be the vertex which is adjacent to $y$ but not to $x$. Notice that $x$ and $y$ must have a common neighbour. Hence they share $k - 1$ elements. Similarly, $x$ and $z$ must have a common neighbour and hence share $k - 1$ elements. Therefore $z$ and $y$ share at least one element (as $k \geq 3$). This is a contradiction to the fact that $z$ and $y$ are neighbours (and thus are disjoint).

Therefore there cannot be a cycle of length $5$.