解答题 （共 12 题 ），解答过程应写出必要的文字说明、证明过程或演算步骤
设图 $G$ 中有 9 个结点, 每个结点的度不是 5 就是 6 。试证明 $G$ 中至少有 5 个 6 度结点或至少有 6 个 5 度结点。
(1) $n(n \geq 1)$ 阶无向完全图与有向完全图各有多少条边?
(2) 完全二部图 $K_{n, m}$ 中共有多少条边?
(3) $n$ 阶 $k$ 正则图中共有多少条边?
寻找一个 $n(n \geq 2)$ 阶简单图 $G$, 使得它的边数 $m$ 为 $\frac{(n-1)(n-2)}{2}$ 。
(1) $m$ 条边的 $n$ 阶无向简单图 $G$ 可产生多少个定向图?
(2) 画出星形图 $K_{1,2}$ 的全部的定向图。
有 $n$ 个药箱, 若每两个药箱里有一种相同的药, 而每种药恰好放在两个箱中, 问共有多少种药品?
某一次聚会的成员到会后相互握手。试用图论的知识说明与奇数个人握手的人数一定是一个偶数。
若有 $n$ 个人, 每个人恰恰有三个朋友, 则 $n$ 必为偶数。
在 $n(n \geq 2)$ 阶简单图 $G$ 中, $n$ 为奇数, 问 $\bar{G}$ 与 $G$ 的奇度结点的个数有何关系?
设 $G$ 为至少有两个结点的简单图, 证明: $G$ 中至少有两个结点度数相同。
证明: 在至少有 2 个人的人群中, 至少有 2 个人, 他们有相同的朋友数。
将无向完全图 $K_6$ 的边随意地涂上红色或绿色, 证明: 无论如何涂法, 总存在红色的 $K_3$ 或绿色的 $K_3$ 。