When is a graph balanced bipartite?

Question

I have a quick question: is there any sufficient condition (theorem, lemma, proposition,...)
to show that a graph (vertices do not have the same degree) is balanced bipartite?

Answer 1

No odd cycles (which guarantees that the graph is bipartite) and regular (aka, all vertices have the same degree).

Answer 2

One sufficient condition is that the graph has two vertices.

If instead you want a necessary and sufficient condition, then you will not find any efficient one, because it can be used to solve bin packing which is NP-hard.

Answer 3

You can always check if all cycles are even, and if so check if each partition has the same size by partitioning into vertices at even and odd distances from a vertex.

But to efficiently check whether a graph is balanced bipartite, I would prefer to do a greedy 2-coloring and check if $\#$vertices with same color are equal. With efficient data structures (adj lists) this can be done in $O(n+m)$ time.

EDIT: This works for connected graphs only, else as user21820 points out, is NP hard. It is kind of surprising to see that adding a simple constraint makes the problem very difficult (from linear).