Skip to main content
2 of 3
added 17 characters in body
Licheng Zhang
  • 1.9k
  • 6
  • 17

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

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.

enter image description here


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.
Licheng Zhang
  • 1.9k
  • 6
  • 17