图的连通度：
割边：删去后使G不连通的边。非平凡树每一条边都是割边。
ps：若G是非连通图，若在某个连通分支上成立，在整个图上也成立，因为割边本质上是使连通度下降的边，所以只讨论连通图即可。
必要性证明：证明G-e是否还是连通图，包含e，若去掉的话，x到y，经过需要走e的路，则用P路代替。
充分性证明：因为（u,v）路P是在G-e上选择的，那肯定不含e，而且也设uv=e，再加回e，肯定会形成圈。
上述定理表明：圈中的边一定不是割边。
割点：去掉它，也会使连通图变为不连通。
ps：G是简单图，无圈无重边。G-v仍连通的话，x和y必定存在一条不经过v的路P，然后再加上原来的xvy，则在G中形成了一个圈，矛盾。无论怎么去掉叶子节点，连通度都不会发生改变。
必要性其实是已经证明了的，割点是无论如何，也不会出现在d(v)=0和d(v)=1的情况上的。
块：没有割点的连通图称为块。
图G的块：子图B是块，G中没真包含B的子图也是快，说明B是最大的块，则B是G的块。
连通度：
度量图的连通程度的两个参数：图的连通度、边连通度。
顶点割或点割：G-V'不连通，则V’为顶点割。完全图没有顶点割。以完全图作为生成子图也没有顶点割。
最小点割：G中点数最少的顶点割。
连通度：最小顶点割中的点数为G的连通度。不存在顶点割，则连通度为n-1。非连通图，则连通度为0。记为。
图是k连通的：一个图的连通度至少为k。
例如：非平凡连通图->1连通的；G连通、无割点且至少含有3个点2连通的。
ps：k连通的，反映的是一个连通图，在目前条件下的一个，连通度的一个下界。
边割：G-E’不连通，则E’为G的边割。含有k条边的边割，称为k边割。
最小边割：边数最少的边割。
边连通度：最小边割集中的，边数数目。记为，对非连通图或平凡图G，λ(G)=0。
图是k边连通的：一个图的边连通度至少为k。
例如：非平凡连通图->1边连通的；G连通、无割边且至少含有两个点2边连通的。
ps：将某点u相关联的所有边，取出形成集合G，必定是一个边割集，因为去掉它，必定会引起不连通。若对含有最小度δ的点，取出所有关联的边，就能引起图G的不连通，因此它的边连通度至多为δ。
情况1：因为H是G已经去掉了一条边e得到的，因此至少要再去掉k-1条边，就会导致不连通，所以λ(H)=k-1。因为H和G都含有完全图作为生成子图，因此H和G都没有顶点割，所以它们的连通度相等，可证得。
情况2：反面就是，H存在顶点割。。若G-S不连通，则至多是。若G-S连通，意味着，再减去e边就不连通了，所以e是割边。连通度最大也就等于n-1，因此有。1顶点割{v}可在割边e的端点处去到。只要存在某一顶点割，则连通度至多是它。
ps：因为最小度δ≥n/2，所以含有最小度的那个顶点，所在的连通分支，必有大于等于n/2个顶点。因此，其它的分支的某个分支的顶点数，有。简单图的最大度，至多为顶点数-1，因此有：。非连通图G的最小度那个点，要么在连通分支H中可得出，要么在另外的连通分支中得出，总之一定比δ(H)小或等于。
ps：若在最小度的那个顶点处，减去(k-1)个顶点，则减去之后，δ(H)可能会变少，例如最小度的点邻接的点被减了，可能会变大，最小度的点被减了，但减少，也只能减少到，在原来最小度δ(G)的基础上，减去(k-1)。
因为任意减去(k-1)个点后，图还是连通的，说明了连通度至少大于k-1，也就是至少为k，因此G是k连通的。
ps：因为p中的每个顶点可贡献多条边与M的多条边相连，因此p不一定等于M。G1至少有p个点，假设G1在原来G中时，每个点的度都为最小度δ(G)，则至少能贡献pδ(G)，然后再减去最小边割集M=λ(G)，就是G1度之和的下界了。与M相关联的p个点，互相连接，所形成的边数还小于G1的边数，则G1的顶点数＞p。和M相关联的点只有p个，则G1其它点只能和自身连。
某个点的度数至少为了，则其所在的连通分支的顶点数，包括它自身在内，也至少为。
敏格尔定理：
例子：
