1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Or even a cycle. $\endgroup$ – pjs36 Nov 14 '15 at 21:09
  • 1
    $\begingroup$ 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... $\endgroup$ – Nick Matteo Nov 15 '15 at 2:25
2
$\begingroup$

Consider an even circle graph.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.