Question

组合数学题求解答

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

Answer 1

首先核对一下术语, 题目里的"图"应该是指简单图, 即每一对顶点间至多有一条边.
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*连通.