Соответствия, сравнения, количества

Докажем, что если есть хотя бы два способа записать так числа, то этих способов четное число. Покрасим вершины четной степени в синий цвет, а вершины нечетной степени — в красный. Заметим, что данная раскраска удовлетворяет условию: у любой синей вершины четное число синих соседей, у любой красной — нечетное число синих соседей. (*)

И наоборот, если раскраска вершин удовлетворяет (*), по ней однозначно восстанавливается расстановка чисел, удовлетворяющая условию. Теперь сделаем ещё одну переформулировку. Поставим в каждую вершину по лампочке и выключателю. При нажатии выключателя в вершине меняют своё состояние лампочка в самой вершине и все лампочки в соседних с ней вершинах. Изначально все лампочки выключены. Тогда множества синих вершин, удовлетворяющих (*), это в точности такие множества вершин, что при нажатии на выключатели во всех вершинах этого множества загораются лампочки во всех вершинах графа. Будем теперь рассматривать способы выбрать множество выключателей, чтобы загорелись все лампочки. Пусть и  — два различных подходящих множества (хотя бы два множества есть по условию). Тогда множество выключателей (симметрическая разность двух множеств) таково, что при нажатии на все выключатели ни одна из лампочек не меняет своего состояния. При этом так как Наконец, легко видеть, что соответствие является разбиением всех подходящих множеств на пары.