ASU 271 All Soviet Union MO 1979 enemies of members of parliament
Source:
July 14, 2019
combinatorics
Problem Statement
Every member of a certain parliament has not more than enemies. Prove that it is possible to divide it onto two subparliaments so, that everyone will have not more than one enemy in his subparliament. ( is the enemy of if and only if is the enemy of .)