离散数学《图论与代数结构》第8周习题

应该用电脑写的，字太多，亏了亏了。既然写完了，就把题抄一下吧。

2.

令 G 是一个有奇数个结点的简单无向图。证明：如果 G 可以被一笔画出，则对于任意的，一定存在某种加边方案，使得给图 G 添加 k 条边之后还可以被一笔画出。方案需满足加边后仍然为简单图。

3.

证明：如果简单无向图 G 的补图是连通图，每个点的度数且至少有一个点，那么 G 有哈密顿回路。