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
$\begingroup$No odd cycles (which guarantees that the graph is bipartite) and regular (aka, all vertices have the same degree).
$\endgroup$ 8 $\begingroup$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.
$\endgroup$ $\begingroup$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).
$\endgroup$ 1
