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$ where $k$ is odd.