1. 第六章 图的基本概念

1.1. 6.3 路、圈、连通图

1.1.1. 6.

在一个有 $n$ 个人的宴会上，每个人至少有 $m$ 个朋友 $(2 \le m \le n)$ 。试证： 有不少于 $m+1$ 个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。

证明：

题目等价于证明：图 $G$ 有 $n$ 个顶点，当 $\delta (G) = m (2 \le m \le n)$ 时， $G$ 存在长度至少为 $m + 1$ 的圈。

设 $G$ 的一条最长路为 $v_1 v_2 \dots v_p$ ，连接 $v_1$ 的至少 $m$ 个点必属于 $\{ v_2, v_3, \dots , v_p \}$ ，否则此不为最长路，即 $p \ge m + 1$ ，故 $\exist i \ge m + 1 , \ s,t. \ v_1 v_i \in G$ ， $v_1 v_2 \dots v_i v_1$ 是 $G$ 的一个长度至少为 $m + 1$ 的圈。证毕。

1.1.2. 10.

设 $G$ 是一个 $(p, q)$ 图，证明：

• (a) 若 $q \ge p$ ，则 $G$ 中有圈；
• (b) 若 $q \ge p + 4$ ，则 $G$ 包含两个边不重的圈。

证明：

• (a)

• (b)

  • [证明 $1$ ] （此法被大佬锤了，因为要求是平面图，而欧拉定理是平面图的必要条件而非充分） 若 $q \ge p + 4$ ，则 $G$ 至少有五个圈（这五个圈不可分割成更小的圈）。 由四色定理，用四种颜色给这五个圈染色。存在一种染色方案，使得若两个圈有公共边，则染不同颜色。此方案下必存在两个圈颜色相同，即其不相邻，故没有重边。[证毕]