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组。