今有n个人已知他们中的任何2个人合起来认识其余的n-2个人证明当n>=3时这n个人能排成1列使得中间的任何人都认识两旁的人而两旁的人都认识左边或右边的人而当n>=4时这n个人能排成一

Question

今有n个人 已知他们中的任何2个人合起来认识其余的n-2个人 证明 当n>=3时 这n个人能排成1列 使得中间的任何人都认识两旁的人 而两旁的人都认识左边或右边的人 而当n>=4时 这n个人能排成一个圆圈 使得每个人都认识两旁的人.
应该证明有哈密顿回路的存在
有+分的···

Answer 1

证明 将这n个人作为n个结点,如果某两个人认识,则这两个人对应的结点之间存在一条边,这样就得到一个具有n个结点的无向图,此时需证明的是,当n>=3时该图存在一个哈密顿路,n>=4时,该图存在一个哈密顿回路,即该图是哈密顿图,下面给出证明.
首先证明当n>=3时该图存在一个哈密顿路.
设u,v是任意两个结点,由本题题意(任何2个人合起来认识其余的n-2个人)可知,deg(u)+deg(v)>=n-2,下面需证明deg(u)+deg(v)>=n-1,否则如果deg(u)+deg(v)=n-2,分下面两种情况讨论：
1）如果u,v邻接,此时deg(u)+deg(v)>=(n-2)+2=n> n-1;
2) 如果u,v不邻接,则其余的n-2个结点仅能与u,v中的一个结点相邻接,设w是这其余的任一结点（由n>=3可知结点w存在的）,由于结点w仅能u,v其中之一邻接,不妨设w与u邻接,与v不邻接,此时结点u和w均不与v邻接,这与题意矛盾；
故deg(u)+deg(v)>=n-1,则该图存在一个哈密顿路（参看任意一本离散数学书,如西北工业大学出版社出版刘长安编著《离散数学教程》P267）.
再证明当n>=4时,该图存在一个哈密顿回路.
下面需证明对任意两个结点u,v有deg(u)+deg(v)>=n,仍分下面两种情况讨论：
1）如果u,v邻接,此时deg(u)+deg(v)>=(n-2)+2=n;
2) 如果u,v不邻接,如果deg(u)+deg(v)=n-1,此时除u,v外其余的结点中存在一个结点s与u,v均邻接,另一个结点w仅与u,v其中之一邻接,（由n>=4可知结点s与w是存在的）,不妨设w与u邻接,与v不邻接,此时结点u和w均不与v邻接,这又与题意矛盾；
故deg(u)+deg(v)>=n,则该图存在一个哈密顿路（参看任意一本离散数学书,同上书P268）.