# Is the hypercube the only connected, regular, bipartite simple finite graph?

Suppose we know that a simple graph (no multiedges or loops) with finitely many vertices is connected, regular (every vertex has the same degree), and bipartite. Must the graph be a hypercube or an even cycle?

• Or even a cycle. – pjs36 Nov 14 '15 at 21:09
• To answer the modified question after you accepted an answer (which isn't a good way to get an ansewr, btw): No, of course not. For instance, a complete bipartite graph on any number of nodes, or a 4-regular graph on 10 nodes, or a 5-regular graph on 10 nodes... – Nick Matteo Nov 15 '15 at 2:25

I'm too greenhorned to be able to draw this out in Tex, but you should be able to draw this out yourself: $V=\{a,b,c,d,e,f\}$, $E=\{(a,b),(c,d),(e,f),(a,d),(c,f),(e,b)\}$.
Every vertex has degree $2$, the partite sets are $\{a,c,e\}$ and $\{b,d,f\}$, the way I draw it out, I get a weird Pac-man with two mouths (this is my stupid way of saying it's connected), and it has $6$ vertices, so it can't be a hypercube.