Problem

Source: Romanian JBTST V 2007, problem 3

Tags: graph theory, combinatorics proposed, combinatorics



At a party there are eight guests, and each participant can't talk with at most three persons. Prove that we can group the persons in four pairs such that in every pair a conversation can take place.