MathDB

There are

n ( \ge 4 )

people and some people shaked hands each other. Two people can shake hands at most 1 time. For arbitrary four people

A, B, C, D

such that

(A,B), (B,C), (C,D)

shaked hands, then one of

(A,C), (A,D), (B,D)

shaked hand each other. Prove the following statements. (a) Prove that

n

people can be divided into two groups,

X, Y ( \ne \emptyset )

, such that for all

(x,y)

where

x \in X

and

y \in Y

x

and

y

shaked hands or

x

and

y

didn't shake hands. (b) There exist two people

A , B

such that the set of people who are not

A

and

B

that shaked hands with

A

is same wiith the set of people who are not

A

and

B

that shaked hands with

B

Problem Statement