哈密尔顿图证明题设G是简单图,删去G中任一边e,则G-e是一棵生成树.证明是哈密尔顿图
问题描述:
哈密尔顿图证明题
设G是简单图,删去G中任一边e,则G-e是一棵生成树.证明是哈密尔顿图
答
根据题意可得g为一个有回路的简单图,然后假设有点不再回路上,去掉与这个点相连的边,与G-e是一棵生成树是一颗生成树矛盾,所以所有点必在这个回路上,所以必为哈密尔顿图