连通度定理3若G是2边连通图，则G有强连通的定向图
证明 设G是2边连通图，则G必含有圈
先取一个圈 ，归纳地定义G的连通子图序列 如下： ；若 不是G的生成子图，设 是在G中而不在 中的一个顶点，则存在从 到 的边的不重路 和 ，定义 ，由于 ，这个序列必然终止于G的一个生成子图
现依次给每个 定向：首先让 的定向图 成为一个有向圈；对 ，设已有定向图 ，让 成为以 为起点的有向路，而 成为以 为终点的有向路得 ，易见 是强连通有向图
因此最后的 是强连通有向图
由于 是G的生成子图，所以G有强连通的定向图
显然，一个图G有强连通的定向图的必要条件是G为2边连通的
否则G中有割边，这与G有强连通的定向图矛盾
证毕
以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。
