组合数学第四版（RichardA.Brualdi）第11章的几道课后题(8、20、21).被采纳的一定追加分数.一共3道

首先核对一下术语,题目里的"图"应该是指简单图,即每一对顶点间至多有一条边.
21题中的"一般图"才是一般意义上的图,允许多条边和起点终点重合的边.
8.将G的顶点分为两个子集:由前k个顶点组成的集合A,和后n-k个顶点组成的集合B.
在和式∑{1 ≤ i ≤ k} di中,A中顶点之间的边被计数两次,A中顶点与B中顶点之间的边被计数1次.
因此有不等式∑{1 ≤ i ≤ k} di ≤ 2·A内部的边数+A到B的边数,两部饭分别估计.
①因为G是简单图,A有k个顶点,故A内部的边数 ≤ C(k,2) = k(k-1)/2.
②A到B的边数 = ∑{k+1 ≤ i ≤ n} 第i个顶点到A的边数.
易见,第i个顶点到A的边数 ≤ di,且第i个顶点到A的边数 ≤ k.
故A到B的边数 ≤ ∑{k+1 ≤ i ≤ n} min{k,di}.
综合得∑{1 ≤ i ≤ k} di ≤ k(k-1)+∑{k+1 ≤ i ≤ n} min{k,di},即所求证.
20.用反证法,假设图不连通,则可将图分成两个子图的无交并.
设两个子图分别为k阶和n-k阶,1 ≤ k ≤ n-1.
作为简单图,二者的边数分别至多为C(k,2)和C(n-k,2).
因此原图边数 ≤ C(k,2)+C(n-k,2)
= (k²-k+(n-k)²-(n-k))/2
= (k²+(n-k)²-n)/2
= (n²+(n-2k)²-2n)/4
≤ (n²+(n-2)²-2n)/4 (1 ≤ k ≤ n-1)
= (n-1)(n-2)/2,
与至少有(n-1)(n-2)/2+1条边矛盾.
例子:一个n-1阶完全图恰有(n-1)(n-2)/2条边,添加一个孤立点即可.
21.基本事实:一个图中奇顶点的个数必为偶数.
设G中包含x的连通分支为H,由H包含奇顶点x,H至少还包含一个奇顶点.
但G中只有两个奇顶点x和y,故H包含y.
G中已存在x到y的路径,因此添加新边{x,y}不改变G的连通性.
即G连通当且仅当G*连通.