电大离散数学图论部分期末复习辅导(4)

离散数学期末复习辅导（二）

五、证明题

证明题同学一般都做不好，原因是对证明题方法没有掌握，也是对一些概念不清楚所造成的。因此，希望大家认真学习教材和老师讲课中的证明方法，并通过作业逐步掌握做证明题的方法。

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库电大离散数学图论部分期末复习辅导(4)在线全文阅读。