A group of people is said to be good if every member has an even number (zero included) of acquaintances in it. Prove that any group of people can be partitioned into two (possibly empty) parts such that each part is good.
Source: 2021 Macedonian Team Selection Test P3
Tags: combinatorics, graph theory
A group of people is said to be good if every member has an even number (zero included) of acquaintances in it. Prove that any group of people can be partitioned into two (possibly empty) parts such that each part is good.