Question

1.证明：若无向图G不连通,则G的补图是连通的

Answer 1

求证：每个连通图G至少有两个顶点不是割点.

证明：令u和v是在G中有最大距离的两顶点.又假定v是割点,则有一顶点w,它与u在G-v的不同的支中.从而v在每一条联结u和w的通路上,所以d(u,w)>d(u,v).这是不可能的,故顶点v,类似的顶点u,不是割点.

根据定理（每个连通图G至少有两个顶点不是割点）和定理（设v是树T的一个顶点,则当且仅当deg v>1时,v才是T的割点）可以直接得出下面的推论,

推论：每一棵树至少有两个度为1的顶点,且树中最长通路的起点和终点的度均为1.