Question

请教一道数学图论题

大家好，这道题涉及到计算机的图论，不一定要全部帮我做出，只要能大部分给出结果，我就会全部分给上并且追加更多分，题目如下：

假设有一群（大于等于3）人，他们中的每个人都认识至少一半以上的剩下的人，那么他们可以被安排在一个圆桌上，而且每个人左右两旁的两个人都是他认识的。
（1）。此命题等价于在一个图中一个寻找Hamiltonian（汉米尔顿） 回路。所以第一步，您需要把原命题画为图，并给出节点，边，并说明当这个图满足什么样的条件时，存在一个Hamiltonian（汉米尔顿） 回路。
（2). 请用反证法来证明，即：如果图中不存在Hamiltonian（汉米尔顿） 回路 的话，把不相邻的两个节点用线相连的话不会产生一个Hamiltonian（汉米尔顿） 回路。从中您会得到什么启示？
（3).运用上面的结论，请您在图中任选两个不相邻的节点并研究它们的连接情况。(2)中的“不存在Hamiltonian（汉米尔顿） 回路的条件” 和 两个节点的连接情况有什么
联系？

我感觉这道题完全就是考察Hamiltonian（汉米尔顿） 回路相关的知识，我只知道Hamiltonian（汉米尔顿） 回路 是指图形中一条只访问每个节点一次的回路。但是这个问题我不知道怎么去思考了，还请擅长这方面的朋友多多帮忙，给点思路或者解答，我会追加更多的分的，谢谢！

Answer 1

嗯……其实图论完全没学过……就会第二小问：
假设存在一个满足题意的图，其中没有Hamiltonian回路，但是加入一条边后就会产生Hamiltonian回路。
根据假设和题意，原图中存在一个形如x1-x2-...-xn的链，且x1与xn不相邻。
如果在存在i(2<=i<=n-2)，使得xn-xi,x1-x(i+1)，那么存在Hamiltonian回路：x1-...-xi-xn-x(n-1)-...-x(i+1)-x1。由此与假设矛盾，原命题成立。
下用反证法正面i的存在性。
假设这样的i不存在。
由题意与x1相邻的点的数目m1>(n-1)/2，由假设，将这些点的下标减1，得到的另外m1个点不能与xn相邻。考虑到x2与x1相邻，于是在x2到x(n-1)这n-2个点中，已经有至少m1-1个点不能与xn相邻，又有x1不与xn相邻，于是与xn相邻的点的数目m2满足：
m2<n-2-(m1-1)=n-m1-1<(n-1)/2
与题目条件矛盾。于是假设不成立，i一定存在。证毕。
由第二小问可知如果存在一个满足题目条件、不存在Hamiltonian回路的图，那么在其上加上有限条边也无法再其中产生Hamiltonian回路。这显然是矛盾的，因为满图有有限条边且存在Hamiltonian回路。于是由反证原来可知满足题设的图必然存在Hamiltonian回路。

Answer 2

dr tryrtdtdjtd rtrd ye1t 0a12