问答题
设图G是具有8个顶点的无向简单图,图中有一个顶点的度数为2,删去这个2度点后,所得的主子图为7阶完全图K7。证明图G是哈密顿图。
【正确答案】[证明]介绍两种证明方法。
方法1:设图G中的8个顶点分别为v1,v2,…,v7,v8,并设v8是2度点,删去2度点v8后,所得的子图是7阶无向完全图K7。由于K7中任意两点都有边相连,所以v1,v2,…,v7的任意一种排列都能构成一个K7的哈密顿回路。
而v8是2度点,设v8与v1,v2,…,v7中的两个不同的顶点vi和vj邻接,由此可得到图G的哈密顿回路为v1→v2→…→vi→v8→vj→…→v1。例如,v8与v3、v5邻接,则可得到图G的哈密顿回路为v1→v2→v3→v8→v5→v4→v6→v7→v1。由此证得,图G是哈密顿图。
方法2:由于7阶无向完全图K7中的每个顶点都为6度点,而v8又是2度点,所以图G中8个顶点的度数为2,6,6,6,6,6,8,8。由此可见,图G中任意不同两个顶点的度数之和大于等于8,所以图G是哈密顿图。
【答案解析】