How can one construct a class of $k$-connected $k$-regular bipartite graphs with the girth of (at most) $k-1$?

Question

I would like to construct a class of $k$-connected $k$-regular bipartite graphs with the girth at most $k-1$.

This problem arises from a cycle.

• Any 2-connected 2-regular graph is a cycle, but its girth is $n$ (the number of vertices in the cycle).
• For a $3$-regular graph, its girth cannot be less than or equal to $2$. The same applies to $4$-connected $4$-regular bipartite graphs, where the girth cannot be less than 3.

Therefore, this problem may be meaningful starting from $k=5$. While I may have found some examples, I would like to ask whether there is a unified pattern for such graphs.

For example, $k=5$, we can find the following bipartite graph such that $5$-reguler $5$-regular with girth $4$. I believe such graphs are infinite.

---

The second question is, if I limit the girth to be $k-1$ can we still find infinitely many such graphs? That is to say,

• Construct a class of $k$-connected $k$-regular bipartite graphs with the girth of $k-1$ if $k$ is odd and of $k-2$ if $k$ is even.

Answer 1

I'll answer for $k=5$ and leave the remaining cases for you to generalise.

For $n \geqslant 5$, let $X_n$ denote the Cayley graph $\mathrm{Cay}(\mathbb{Z}_{2n},\{\pm 1, \pm 3, n\})$.

Claim

The graph $X_n$ is always $5$-regular, it is bipartite if and only if $n$ is odd, and it always has vertex-connectivity equal to $5$.

Proof

The claims about the regularity and bipartite-ness are obvious, so it is only the claim about vertex-connectivity that requires proof.

For this we use results from Watkins' seminal 1970 paper "Connectivity of Transitive Graphs".

From Lemma 4.1, if the connectivity is not $5$, then it is of the form $rp(X_n)$ where $r \geqslant 2$ and $p(X_n)$ is the size of an atomic part, where an atomic part is the smallest possible connected component obtained by removing from $X_n$ a cutset of size less than $5$.

So if the connectivity is less than $5$, then it must be $4$ and it must be the case that $r=2$ and $p(X_n) = 2$.

If $p(X_n) = 2$, then $X_n$ has an atomic part that is just a single edge, and, by the comment immediately before Lemma 4.1, this edge must be a block of a system of imprimitivity of $\mathrm{Aut}(X_n)$.

The cyclic group only has one system of imprimitivity with blocks of size 2, namely the set of diagonal edges (edges of the form $\{x,x+n\}$). But the endpoints of the edge $\{0,n\}$ have, collectively, more than $4$ neighbours, and so this is not an atomic part.

This contradiction shows that the connectivity is not less than $5$, and hence it must be exactly $5$.