PDF《图的连通性》

25 ? |G1| ? ?G ? ?v∈G1d(v)? |G1|?(|G1| -1)+ |G1| ? |V'| ? ?G ? |G1| -1+ |V'| ? (n-|V'|)/2 + |V'| -1 ? 2?G ? n-2 + |V'|? ?G+ |V'| , 所以 |V'| ??G ? 所以 ?(G) ? ?G G1 V' G2 连通度与点不相交的通路 (现象:对图G中任意两点u,v, 如果点不相交的uv-通路有k条,显然, 要使u,v不连通, 至少须删除k个顶点.) ? Whitney定理: 图G(|G|?3)是2-连通图 当且仅当 G中任意两点被至少2条 除端点外顶点不相交的路径所连接. 注意:"G中任意两点被至少2条除端点外顶点不相交的路径所连接"等 价于"任意两点均处在同一初级回路中" .

26 Whitney定理的证明 ? ?显然 ? ?:设u,v是图G中的任意两点.下面对距离d(u,v)进行归纳. 当d(u,v)=1, uv?EG, 因为G是2-连通图,G-uv仍连通,则G中除边uv外, 必有另一条不含uv的路径. 假设当d(u,v)