در یک مهمانی ۷ نفر حضور دارند. میدانیم که هر نفر حداقل با سه نفر دیگر آشناست. آیا همواره میتوان این ۷ نفر را به گونهای دور یک میز نشاند که هر دو نفری که در کنار هم نشستهاند باهم آشنا باشند؟
پاسخ
فرض میکنیم a با همهی افراد٬c،b و d دو به دو باهم و f،e و g نیز دو به دو باهم آشنا باشند و هیچ آشنایی دیگری موجود نباشد.
بدون این که به کلیت مسئله لطمهای وارد شود فرض میکنیم سمت چپ a نفر b باشد، دراین صورت سمت چپ b یا باید c نشسته باشد و یا d. در حالت اول نفر بعدی (نفر چهارم)d و در حالت دوم نفر بعدی c خواهد شد٬ ولی معلوم است که فردی که با d( یا c) آشنا باشد پیدا نمیشود تا در جایگاه پنجم بنشانیم.