Problem #PRU-78529

Graph Theory Problems Methods Pigeonhole principle Pigeonhole principle (other)

Problem

A group of \(2n\) people were gathered together, of whom each person knew no less than \(n\) of the other people present. Prove that it is possible to select 4 people and seat them around a table so that each person sits next to people they know. (\(n \geq 2\))