今有2K（K>=2）个人去完成K项任务.已知每个人均能与另外2K-1个人中的的K个人中的任何人组成小组（每组两个人）去完成他们共同熟悉的任务,证明这2K个人一定能够分成K组（每组两个人）,每

Question

今有2K（K>=2）个人去完成K项任务.已知每个人均能与另外2K-1个人中的的K个人中的任何人组成小组（每组两个人）去完成他们共同熟悉的任务,证明这2K个人一定能够分成K组（每组两个人）,每组完成一项他们共同熟悉的任务.

Answer 1

设　V={v|v是去完成任务的人},
　　　　E={(u,v)|u,v∈V且u≠v且u,v能组成小组}
　　则得2k阶无向简单图G.由已知条件,任意u,v∈V,
　　　　d(u)+d(v)≥2k
　　由定理15.7的推论可知,G为哈密顿图.于是存在哈密顿回路.设C=vi1vi2...为其中的一条哈密顿回路,在C中相邻的顶点都能组成二人小组.所以可以分成k组.