习题三：
?
证明：是连通图G的割边当且仅当V(G)可划
分为两个子集V1和V2，使对任意证明：充分性: 是的割边，故个连通分支的顶点集，的及, G中的路必含. 是其中一至少含有两个连通分支，设是其余分支的顶点集，对?u?V1,?v?V2，因为中路上，中的必不连通，而在中与连通，所以在每一条含。
必要性：取u?V1,v?V2，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以e是割边。 ? 价： （1） （2）
个圈上；
（3）
：
是块，任取的一点，一边，在边插入一点，使得成为两条边，由，显然的是阶数大于3的块，由定理，中的u,v位于同一
G无环且任意三个不同点都位于同一条路上。 3.设G是阶大于2的连通图，证明下列命题等G是块
G无环且任意一个点和任意一条边都位于同一
此得到新图个圈上，于是
中u与边都位于同一个圈上。 ：
无环，且任意一点和任意一条边都位于同一个圈上，任取的点u，边e，若在上，则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v，由此得到新图显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。
， ：
连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，x?v1,y?v2，点在每一条
?
是补图的割点。
证明：是单图的割点，则果在不在的路上，则与已知矛盾，是块。
7.证明：若v是简单图G的一个割点，则v不
有两个连通分支。现任取, 如
的同一分支中，令是与在处于不同分支的点，那么，与的补图中的补图中连通。若的同一分支中，则它们在邻接。所以，若是的割点，则不是补图的割点。 ?
12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。
解：??G1??2 最小点割 {6,8}
?(G1)?2 最小边割{（6,5），（8,5）}
??G2??5 最小点割{6,7,8,9,10}
?(G2)?5 最小边割{（2,7）…（1,6）}
?
能k(H)> k(G). 解： 通常. 13.设H是连通图G的子图，举例说明：有可
e H
整个图为，割点左边的图为的的子图，
，则
.
图论及其应用第三章答案电子科大
