离散数学期末复习辅导（二）
五、证明题
证明题同学一般都做不好，原因是对证明题方法没有掌握，也是对一些概念不清楚所造成的。因此，希望大家认真学习教材和老师讲课中的证明方法，并通过作业逐步掌握做证明题的方法。
1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．
证明 设G??V,E?，G??V,E??．则E?是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结点u?V，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于3的奇数，从而Kn的每个结点都是偶数度的（n?1 (?2)度），于是若u?V在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．
2．设连通图G有k个奇数度的结点，证明在图G中至少要添加欧拉图．
证明 由定理3.1.2知，k必为偶数．要使这k个奇数度结点变成偶数度结点，从而使
k图G变成欧拉图，可在每两个奇数度结点间添加一条边．故在图G中至少要添加2条
k条边才能使其成为2边才能使其成为欧拉图．
16