这道题涉及到计算机的图论,不一定要全部帮我做出,只要能大部分给出结果,我就会全部分给上并且追加更多分,假设有一群（大于等于3）人,他们中的每个人都认识至少一半以上的剩下的人,那

Question

这道题涉及到计算机的图论,不一定要全部帮我做出,只要能大部分给出结果,我就会全部分给上并且追加更多分,
假设有一群（大于等于3）人,他们中的每个人都认识至少一半以上的剩下的人,那么他们可以被安排在一个圆桌上,而且每个人左右两旁的两个人都是他认识的.
（1）.此命题等价于在一个图中一个寻找Hamiltonian（汉米尔顿） 回路.所以第一步,您需要把原命题画为图,并给出节点,边,并说明当这个图满足什么样的条件时,存在一个Hamiltonian（汉米尔顿） 回路.
（2).请用反证法来证明,即：如果图中不存在Hamiltonian（汉米尔顿） 回路 的话,把不相邻的两个节点用线相连的话不会产生一个Hamiltonian（汉米尔顿） 回路.从中您会得到什么启示?
（3).运用上面的结论,请您在图中任选两个不相邻的节点并研究它们的连接情况.(2)中的“不存在Hamiltonian（汉米尔顿） 回路的条件” 和 两个节点的连接情况有什么
联系?
我感觉这道题完全就是考察Hamiltonian（汉米尔顿） 回路相关的知识,我只知道Hamiltonian（汉米尔顿） 回路 是指图形中一条只访问每个节点一次的回路.但是这个问题我不知道怎么去思考了,还请擅长这方面的朋友多多帮忙,给点思路或者解答,我会追加更多的分的,

Answer 1

嗯……其实图论完全没学过……就会第二小问：
假设存在一个满足题意的图,其中没有Hamiltonian回路,但是加入一条边后就会产生Hamiltonian回路.
根据假设和题意,原图中存在一个形如x1-x2-...-xn的链,且x1与xn不相邻.
如果在存在i(2