连通度定理1对一个图G，有
其中 是图G的最小顶点度
证明 若G不连通，则 ．故上式成立
若G连通，则： (1)先证
设x是G中度数最小的顶点，即 ，设所有与x关联的边集为S (x)，显然x是图G-S(x)的一个孤立结点
于是
(2)再证
当 时，显然有
假设对所有 的图G，有
再设 ，S是H的一个边割，且
若边 ，易知 ，故由假设知 ，并设T是 的一个点割，且
而此时 就是H的一个点割，即由归纳法原理知
证毕
以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。
