Говорят, что граф двудольный, если его вершины можно разбить на две доли так, чтобы внутри каждой доли рёбер не было.
Нетрудно заметить, что в таком графе сумма степеней вершин одной доли должна быть равна сумме степеней другой.