MathDB

In a set

X

of n people, some know each other and others do not, where the relationship to know is symmetric; that is, if

A

knows

B

. then

B

knows

A

. On the other hand, given any

4

people:

A, B, C

and

D

: if

A

knows

B

B

knows

C

and

C

knows

D

, then it happens at least one of the following three:

A

knows

C, B

knows

D

A

knows

D

. Prove that

X

can be partition into two sets

Y

and

Z

so that all elements of

Y

know all those of

Z

or no element in

Y

knows any in

Z

Problem Statement