（7） R （6） （8） R??R （5），（7） 五、证明
1．设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e?0。 证明：
用反证法证明。假设e=0。
对A的任一元素a，因为e和0是A上关于二元运算*的单位元和零元， 则a=a*e=a*0=0。即A的所有元素都等于0,这与已知条件|A|>1矛盾。 从而假设错误。
2．任一图中度数为奇数的结点是偶数个。 证明：
设G=〈V,E〉是任一图。设|V|=n。 由欧拉握手定理可得
?v?Vdeg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数
之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。 3．设群＜G,*＞除单位元外每个元素的阶均为2，则＜G,*＞是交换群。 证明：
对任一a?G，由已知可得a*a=e，即a=a。
对任一a,b?G，因为a*b=(a*b)=b*a=b*a，所以运算*满足交换律。 从而＜G,*＞是交换群。
4．在一个连通简单无向平面图G=〈V,E,F〉中若|V|?3，则 |E|?3|V|－6。 证明：
因为|V|?3，且G=〈V,E,F〉是一个连通简单无向平面图， 所以对任一f?F，deg(f)?3。 由公式
-1
-1
-1-1
?f?Fdeg(f)=2|E|可得，2|E|?3|F|。
再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+所以|E|?3|V|－6。 5．单位元有惟一逆元。 证明：
2|E|?2。 3设
因为e是关于运算?的单位元，所以e1=e1*e=e=e2*e=e2。 即单位元有惟一逆元。
6．设
第 11 页 共 14 页
证明：
因为a*b∈G，且a*(a*b)=(a*a)*b=e*b=b，所以对于a,b∈G，必有x=a-1*b∈G，使得a?x=b。 若x1,x2都满足要求。即a?x1=b且a?x2=b。故a?x1=a?x2。 由于*满足消去律，故x1=x2。
从而对于a,b∈G，必有唯一的x∈G，使得a?x=b。 7．代数系统
设e是该群的单位元。若a是
8．若连通简单无向平面图G有n个结点，m条边，p个面，且每个面至少由k(k?3)条边围成， 则 m?k(ｎ－2)／(ｋ－2)。 证明：
设连通简单无向平面图G=〈V,E,F〉，则|V|=n,|E|=m,|F|=p。 由已知对任一f?F, deg(f)?k。 由公式
-1
-1
-1
?f?Fdeg(f)=2|E|可得，2|E|?k|F|。
再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+即k(n-2)?(k-2)m。 所以m?k(ｎ－2)／(ｋ－2)。
2|E|?2。 k9．证明：证明在元素不少于两个的群中不存在零元。 证明：（用反证法证明）
设在群
因为
设
对G中任一非单位元a。设a的阶为k,则k?1。
由拉格朗日定理，k是p的正整因子。因为p是素数，故k=p。 即a的阶就是p，即群G的阶。故a是G的生成元。
11．设G=〈V,E〉是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。 证明：（用反证法证明）
设|V|=n，则|E|=n-1。 由欧拉握手定理可得
?v?Vdeg(v)=2|E|=2n-2。
因为G连通，所以?v?V，deg(v)?1。假设G中没有1片树叶，则得出矛盾。
?v?Vdeg(v)?2n>2n-2。
12．给定连通简单无向平面图G=
第 12 页 共 14 页
证明：
因为|V|=6?3，且G=〈V,E,F〉是一个连通简单无向平面图， 所以对任一f?F，deg(f)?3。 由欧拉公式|V|-|E|+|F|=2可得|F|=8。 再由公式
?f?Fdeg(f)=2|E|，
?f?Fdeg(f)=24。
因为对任一f?F，deg(f)?3，故要使上述等式成立， 对任一f?F，deg(f)=3。 13．证明在一个群中单位元是惟一的。 证明：
设e1,e2都是群〈G,*〉的单位元, 则e1=e1*e2=e2。 所以单位元是惟一的。 14．在一个群〈G,*〉中，若G中的元素a的阶是k，即 | a |=k，则a的阶也是k。 证明：
因为| a |=k，所以a=e。即（a）=(a)=e。 从而a的阶是有限的，且|a|?k。 同理可证，a的阶小于等于|a|。 故a的阶也是k。
15．若n个结点的连通图中恰有n-1 条边，则图中至少有一个结点度数为1。 证明：（用反证法证明）
设G=〈V,E〉有n-1条边且|V|=n-1。 由欧拉握手定理可得
-1
-1
-1
-1
k
-1
k
k-1
-1
?v?Vdeg(v)=2|E|=2n-2。
因为G是连通图，所以G中任一结点的度数都大于等于1。
假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故得出矛盾。
16、设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e?0.
证明：
（用反证法证明）假设e=0.
对A的任一元素a，因为e和0是A上关于二元运算*的单位元和零元， 则a=a*e=a*0=0. 即A的所有元素都等于0,这与已知条件|A|>1矛盾. 从而假设错误. 即e?0.
17、设T=
（用反证法证明）设|V|=n.
因为T=〈V,E〉是一棵树，所以|E|=n-1.
第 13 页 共 14 页
?v?Vdeg(v)?2n>2n-2。
由欧拉握手定理可得
?v?Vdeg(v)=2|E|=2n-2.
假设T中最多只有1片树叶，则得出矛盾。
?v?Vdeg(v)? 2(n-1)+1>2n-2.
18、若n阶连通图中恰有n-1 条边，则图中至少有一个顶点度数为1. 证明：
（用反证法证明）设G=
?v?Vdeg(v)=2|E|=2n-2.
因为G是连通图，所以G中任一顶点的度数都大于等于1.
假设G中不存在度数为1 的顶点，则G中任一顶点的度数都大于等于2. 故2n>2n-2.
得出矛盾.
19、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点. 证明：
若顶点个数小于等于3时，结论显然成立.
当顶点多于3 个时，用反证法证明. 记|V|=n,|E|=m,|F|=k. 假设图中所有顶点的度数都大于等于5. 由欧拉握手定理得
?v?Vdeg(v)?
?v?Vdeg(v)=2|E|得 5n?2m.
又因为G=〈V,E,F〉是一个连通简单无向平面图，所以对每个面f，deg(f)?3. 由公式
?f?Fdeg(f)=2|E|可得，2m?3k.
再由欧拉公式|V|-|E|+|F|=2可得2?从而30?m，这与已知矛盾.
221m-m+m=m 5315第 14 页 共 14 页
《离散数学》题库及答案
