西安电子科技大学S6.4.2汉密尔顿图软件学院家家证明（1）首先，证明G是连通的（反证法）假设G中存在两个或更多个互不连通的分支。设G中的结点vi和vj分别属于两个不同的连通分支G1和G2，其中G1和G2分别有n1和n2个结点。显然，nl<n且n2<n，于是有deg(vi)<nl-1且deg(vj) ≤n2-1, 则deg(vi)+deg(vi) ≤n1+n2-2=n2。这与已知题设矛盾，假设错误，G是连通的。西安电子科技大学 §6.4.2 汉密尔顿图 软件学院 证明 （1）首先，证明G是连通的（反证法）。 假设G中存在两个或更多个互不连通的分支。设G 中的结点vi和vj分别属于两个不同的连通分支G1和 G2，其中G1和G2分别有n1和n2个结点。 显然，n1<n且n2<n，于是有deg(vi) ≤n1-1且 deg(vj) ≤n2-1, 则deg(vi)+deg(vj) ≤n1+n2-2=n- 2。 这与已知题设矛盾，假设错误，G是连通的