Двудольные графы и переформулировки к ним

Рассмотрим двудольный граф. Вершины в первой доли будут отвечать за людей, а во второй доли за задачи. Ребро между вершинами будет, если школьник решил задачу. Заметим, что тогда у нас условие, что степень каждой вершины в графе равна Тогда попробуем начать путь из какой-нибудь вершины и идти так, пока не зайдем в вершину, в которой мы уже были. Заметим, что если путь начался в вершине то и закончим его мы тоже в вершине так как если мы зациклимся раньше, то будет вершина со степенью три. Следовательно, весь граф является объединением не пересекающихся простых циклов. В каждом из циклов выделим ребра через один и так разберем задачи.