更新时间：2023-01-06 06:43
连通图G的连通程度通常叫做连通度(Connectivity)。连通度有两种，一种是点连通度，另一种是边连通度。通常一个图的连通度越好，它所代表的网络越稳定。
如果在图G中删去一个结点x后，图G的连通分支数增加，即 ，则称结点x为G的割点(cut vertex)。如果在图G中删去一条边e后，图G的连通分支数增加，即 ，则称e为G的割边(cut edge)或桥。
没有割点的非平凡连通图称为块( block)。G中不含割点的极大连通子图称为图G的块。
若H是图G的块，则H自身不含割点且满足：若向H中再添加边，但不添加结点，那么H就不是G的子图了；若向H中再增加结点或边将H扩大为更大的连通图，那么H就会含有割点。
例如，图1所示图G的块如图2所示。
如果图G的顶点集的一个真子集T满足G-T不连通或是平凡图，则称T为G的一个点割( vertex cut)。如果图G的边集的一个真子集S满足G-S不连通或是平凡图，则称S为G的一个边割(edge cut)。
设G是连通图，称 为G的点连通度( vertex connectivity)或连通度；称 为G的边连通度(edge conncctivity)。
对一个图G，有 。其中 是图G的最小顶点度。
证明 若G不连通，则 ．故上式成立。若G连通，则：
(1)先证 。
设x是G中度数最小的顶点，即 ，设所有与x关联的边集为S (x)，显然x是图G-S(x)的一个孤立结点。于是 。
(2)再证 。
当 时，显然有 。
假设对所有 的图G，有 。再设 ，S是H的一个边割，且 。若边 ，易知 ，故由假设知 ，并设T是 的一个点割，且 。而此时 就是H的一个点割，即
由归纳法原理知 。证毕。
定义如果无向图G的连通度 ，则称图G是n连通的或G为n连通图。若 ，则称图G是n边连通的或G为n边连通图。
设图G是n连通的， ，则 。
证明 假设G有一个顶点y且 ，即y与n一1条边关联。设与y关联的n一1个顶点构成的集合为S，显然S是G的一个点割。因而 。这与 矛盾。
若G是2边连通图，则G有强连通的定向图。
证明 设G是2边连通图，则G必含有圈。先取一个圈 ，归纳地定义G的连通子图序列 如下： ；若 不是G的生成子图，设 是在G中而不在 中的一个顶点，则存在从 到 的边的不重路 和 ，定义 ，由于 ，这个序列必然终止于G的一个生成子图 。现依次给每个 定向：首先让 的定向图 成为一个有向圈；对 ，设已有定向图 ，让 成为以 为起点的有向路，而 成为以 为终点的有向路得 ，易见 是强连通有向图 。因此最后的 是强连通有向图。由于 是G的生成子图，所以G有强连通的定向图。显然，一个图G有强连通的定向图的必要条件是G为2边连通的。否则G中有割边，这与G有强连通的定向图矛盾。证毕。