电子科大-杨春-图论第二次作业(共4页).docx

精选优质文档-倾情为你奉上第四章3.7.证明：因为G中无奇点，去除度为零的点，则G中必可以找到一条Eular闭迹，也就是初始圈C1，之后去掉C1所包含的边，去点度为零的点，则在新图G 中每个点的度数仍为偶数，在G中可以找到一条Eular闭迹，也就是圈C2，以此类推，可以寻到C3、.、Cm，最后可以得到。10.证明：(1) 如果G不是二连通的，则G存在割点或者不是连通的。若G不是连通的，则G不是Hamilton图；若G中存在割点v，则G-v的连通分支数大于等于2，由定理：若G是H图，则对于V的每个非空子集S，均有可知，G为非H图。(2) 不妨设|X|X|，由（1）中的定理可知，G为非H图。12.证明：假设G中新加入的一点，为V，它和G中的每一个顶点均相连，这样得到新的图,这样的度序列为。因为不存在正整数m(n+1)/2,使其满足dmm和dn-m+1n-m,即不存在mn/2,满足dm=mm+1和dn-m+1n-m+1 = (n+1)-m。