设G为n阶无向简单图，若G不连通，证明G的补图G必连通．

设G为n个结点的无向简单图,若x(G)≥k,则称G是k-连通图,k为非负整数.证明以下结论:

(1)当时,正明G连通.

(2)当时,证明G是k-连通图.

设n阶m条边连通的无向图G是3-正则平面图，G中次数为i的面为S_i个，证明：。

证明定理15.8.

定理15.8：设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+d(v)≥n,则G为哈密顿图GU(u,v)为哈密顿图((u,v)是加的新边.

设G为n(n≥3且为奇数)阶无向简单图，证明G与G中奇度顶点个数相等．

设G是n(n≥11)阶无向简单图，证明：G或必为非平面图。