练习1。二分图是一组被分解为两个不相交集的图顶点，使得 同一集合内没有两个图顶点是相邻的。设G为二分图，V1和V2为 对应的顶点集。证明G不是哈密顿图。 1） 如果|V1−V2>1。 2） 如果G具有奇数个顶点。

1) 假设G是一个哈密顿图，考虑从V1中的某个顶点v1开始，沿着哈密顿回路依次经过V1中的所有顶点，最后回到v1。因为G是二分图，所以在沿着哈密顿回路从v1到v2的过程中，v2一定属于V2，然后在从v2到v3的过程中，v3一定属于V1，以此类推，最终回到v1时，最后一个顶点一定属于V2。这样，我们就找到了一个属于V2的顶点，与G是二分图矛盾。因此，假设不成立，G不是哈密顿图。

2) 假设G是一个哈密顿图，考虑从V1中的某个顶点v1开始，沿着哈密顿回路依次经过V1中的所有顶点，最后回到v1。因为G是二分图，所以在沿着哈密顿回路从v1到v2的过程中，v2一定属于V2，然后在从v2到v3的过程中，v3一定属于V1，以此类推，最终回到v1时，最后一个顶点一定属于V2。但是因为G有奇数个顶点，所以V1和V2中必有一个集合中的顶点数必须是奇数，所以最后一个顶点既属于V2，又属于V1，与G是二分图矛盾。因此，假设不成立，G不是哈密顿图。