3

Part of 2009 Turkey Team Selection Test

Problems(1)

Every student is sitting next to a friend on both sides

Source: Turkey TST 2009, Problem 6

n\geq 4

some students are friends. In this class any n \minus{} 1 students can be seated in a round table such that every student is sitting next to a friend of him in both sides, but

n

students can not be seated in that way. Prove that the minimum value of

n

10

combinatorics unsolvedcombinatorics