MathDB
Graphs in combinatorics

Source: TST 2014 of Tajikistan

May 20, 2014
extremal principlegraph theorycombinatorics proposedcombinatorics

Problem Statement

There are 1212 delegates in a mathematical conference. It is known that every two delegates share a common friend. Prove that there is a delegate who has at least five friends in that conference.
Proposed by Nairy Sedrakyan