图论与组合数学问题：派对人员圆桌邻座友好排列证明问询

一、证明存在符合要求的圆桌座位安排 #

我们可以把这个问题转化为图论中的哈密顿回路问题来解决：

• 将派对里的每个人抽象成无向图的一个顶点；
• 若两人互为朋友，就在对应的两个顶点之间连一条无向边。

题目里“每个人至少与其中10人互为朋友”的条件，对应到图中就是每个顶点的度数≥10，而总顶点数n=20。

这里可以直接套用Dirac定理：对于n≥3的简单无向图，若每个顶点的度数≥n/2，则该图一定存在哈密顿回路。
因为n=20时，n/2=10，刚好满足每个顶点度数≥10的条件，所以这个图必然存在哈密顿回路。而哈密顿回路对应的就是完美的圆桌座位安排——沿着回路依次排列，每个人的左右邻座都是回路里相邻的顶点，也就是互为朋友的人。

二、解答你的疑惑 #

你提到的“是否意味着每个人仅不认识1个人”是对题目条件的误解：

• 题目只要求每个人至少认识10人，也就是说每个人最多可以不认识20-1-10=9个人（减去自己），完全不是“仅不认识1个人”的硬性要求。
• 你说的“当人数n为奇数时会出现矛盾”，其实是针对“每个人仅不认识1个人”这个错误假设的：如果每个人都恰好不认识1个人，那么总共有n个“不认识”的关系，但不认识是双向的（A不认识B等价于B不认识A），总关系数应该是偶数，当n为奇数时就会出现矛盾。但这个矛盾和原题无关，因为原题并没有要求每个人仅不认识1个人，只是给出了“至少认识10人”的下限，所以不存在这个矛盾。

内容的提问来源于stack exchange，提问作者user529756