MathDB

In a conference there are

n \geq 10

people. It is known that: I. Each person knows at least

\left[\frac{n+2}{3}\right]

other people. II. For each pair of person

A

and

B

who don't know each other, there exist some people

A(1), A(2), \ldots, A(k)

such that

A

knows

A(1)

A(i)

knows

A(i+1)

and

A(k)

knows

B

. III. There doesn't exist a Hamilton path. Prove that: We can divide those people into 2 groups:

A

group has a Hamilton cycle, and the other contains of people who don't know each other.

Problem Statement