m=n+k-2 及
3k?n+k-2 2故 k?2n-4。
98、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。 证明：
若结点个数小于等于3时，结论显然成立。 当结点多于3 个时，用反证法证明。 记|V|=n,|E|=m,|F|=k。
假设图中所有结点的度数都大于等于5。 由欧拉握手定理得
?v?Vdeg(v)=2|E|得 5n?2m。
又因为G=〈V,E,F〉是一个连通简单无向平面图，
所以对每个面f,deg(f)?3。 由公式
?deg(f)=2|E|可得，2m
?3k。
221m-m+m=m 5315f?F再由欧拉公式|V|-|E|+|F|=2可得2?从而30?m,这与已知矛盾。
99、在一个连通简单无向平面图G=〈V，E，F〉中若|V|?3，则 |E|?3|V|－6。 证明：
? |V|?3，且G=〈V，E，F〉是一个连通简单无向平面图，
?
由公式
d(f) ?3，?f?F。
?deg (f)=2|E|可得，2|E|
?3|F|。
2|E|?2。 3f?F再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+
?|E|?3|V|－6。
100、给定连通简单平面图G=
因为|V|=6?3，且G=〈V,E,F〉是一个连通简单无向平面图， 所以对任一f?F，deg(f)?3。 由欧拉公式|V|-|E|+|F|=2可得|F|=8。 再由公式
?deg(f)=2|E|，
f?F?deg(f)=24。
f?F因为对任一f?F，deg(f)?3，故要使上述等式成立， 对任一f?F，deg(f)=3。
101、设G=
用反证法证明。
41
若G 不连通，则它可分成两个独立的子图G1和G2，其中|V(G1)|+|V(G2)|-2=n ，且G1中的任一个顶点至多只和G1中的顶点邻接，而G2中的任一顶点至多只和G2中的顶点邻接。任取u?V(G1),v?V(G2),则 d(u)?|V(G1)|-1, d(v)?|V(G2)|-1。
故d(u)+d(v) ?(|V(G1)|-1)+(|V(G2)|-1)?|V(G1)|+|V(G2)|-2 =n-2 102、一次会议有20人参加，其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？ 证明： 可以。 将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。由已知，图中每个顶点的度数都大于等于10。即图中任两个不相邻的顶点的度数大于等于20，即顶点数。故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可满足要求。 103、证明在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。 证明： 将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。则原命题相当于在该无向图中一定存在两个顶点的度数相等。 设该简单无向图中有n个顶点，则图中n个顶点的度数只能为0，1，2，?，n-1。若图中有两个或两个以上的顶点度数为0，则结论显然成立。否则所有顶点的度数都大于等于1。现用反证法证明该无向图中一定存在两个顶点的度数相等。 设该简单无向图中n个顶点中任何一对顶点的度数都不相等，即这n个顶点的度数两两不同。但每个顶点的度数只能是1,2,?,n-1这n-1个数中的某一种，这显然产生了矛盾。 因此该无向图中一定存在两个顶点的度数相等。从而在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。 104、设有如下有向图G= （1）求G的邻接矩阵；（2）G中v1到v4的长度为4 的通路有多少条？（3）G中经过v1的长度为3 的回路有多少条？（4）G中长度不超过4 的通路有多少条？其中有多少条通路？ 解： （1） ?1?1A=??0??0110??2?1010??，A=??0001???010??0?324?213A=??000??0012 3121?111?? 010??001?2??53?321??，A=??001???0??004 74?43?? 10??01?（2） G中v1到v4的长度为4 的通路有4条； 42 （3） G中经过v1的长度为3 的回路有3条； （4） G中长度不超过4 的通路有72条，其中有19条回路。 ?v ?v 14 ? v2 ?v3 105、求下列无向图中每个顶点的度数；求下列有向图中每个顶点的出度、入度和度。 解： a? ?b ?f 在这个无向图中d(a)=3,d(b)=6, d(c)=4, d(d)=3, d(e)=0, d(f)=0。 c b a 在这个有向图中d(a)=3,d(b)=4, d(c)=3, d(a)=2, d(a)=1, d(b)=2 , d(b)=2,d(c)=1, d(a)=2。 a? ???????d ?e ?c ?d ?e ?c ?b ?f 106、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。 解： c b 它的一个子图 d a e 43 c b f 它的一个生成子图 d a c b 由边集{(a,b),(a,c),(a,d),(b,d)}诱导出的子图 d a b f 由顶点集{a,b,d,f}诱导出的子图 107、求下列赋权图顶点间的距离。 ? d ? a e ? 4 3 5 7 1 c? b ? 14 ?f 解： d(a,b)=3, d(a,c)=3, d(a,d)=?, d(a,e)=8, d(a,f)=16, d(b,c)=1, d(b,d)=?, d(b,e)=6, d(b,f)=13, d(c,d)=?, d(c,e)=5, d(c,f)=12, d(d,e)=?, d(d,f)=?, d(e,f)=7, 108、求下列赋权图中v1到其他顶点的距离。 v2 10 v4 3 v1 2 2 6 4 3 4 v6 v3 2 v5 44