Problem

Source: Czech and Slovak Match 1997 P2

Tags: Set partition, combinatorics



In a community of more than six people each member exchanges letters with exactly three other members of the community. Show that the community can be partitioned into two nonempty groups so that each member exchanges letters with at least two members of the group he belongs to.