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?
3 Answers
No odd cycles (which guarantees that the graph is bipartite) and regular (aka, all vertices have the same degree).
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.
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).
