# What are “different” bipartite regular graphs?

I am struggeling with the idea that there are multiple CONNECTED $$d$$-regular bipartite graphs for fixed degree $$d$$ and number of vertices $$2n$$. If I just draw the vertices in two columns calling the vertices in column 1 $$(v_{1,1},...,v_{1,n})$$ and in column 2 $$(v_{2,1},...,v_{2,n})$$ and draw the corresponding edges then in my head for any other $$d$$-regular bipartite graph I can just apply permutations to $$\sigma_1,\sigma_2$$ to column 1 and column 2, respectively, and I obtain any other CONNECTED bipartite regular graph.

Are there multiple $$d$$-regular bipartite graphs in the sens that they are qualitatively different? Like for normal $$d$$-regular graphs where the properties may vary a lot between different example?

EDIT: I should emphasize that I am talking about connected graphs!

• For $d=0,1,2,n,n-1,n-2$, there is only one possible such graph, up to permutations. Otherwise, there could be different graphs – Exodd Apr 14 at 15:48
• This website (hog.grinvin.org/Cubic) lists cubic (that is, $3$-regular) graphs by vertex count and girth, restricted to connected graphs, and additionally has a table restricting the lists to bipartite graphs. The smallest example of what you're looking for is the two distinct $10$-vertex $3$-regular bipartite connected graphs. – mjqxxxx Apr 14 at 17:12

Already for $$d=2$$ you can have different possibilities based on what the connected components look like. If $$2n=8$$, for instance, the vertices can be arranged in a single $$8$$-cycle, or in two $$4$$-cycles. For larger $$d$$, you have even more flexibility.
If you want a connected example, then we'll need $$d \ge 3$$, just as with ordinary $$d$$-regular graphs. But we can still find an easy counterexample if we take bipartite complements (that is, change adjacencies between the two halves only). For example, the bipartite complement of $$C_4 \cup C_6$$ and the bipartite complement of $$C_{10}$$ are non-isomorphic $$3$$-regular graphs on $$10$$ vertices.
Really, the greatest variety is found in the cases I'm not looking at: $$3 \le d \le n-3$$. But those are also harder to describe, and harder to check for isomorphism.
• So take bipartite complements and now you're looking at many different connected $(n-2)$-regular bipartite graphs. – Misha Lavrov Apr 14 at 16:44