综合挑战:图论与构造

完全图 $K_8$ 有多少条边?

$C_8^2 = \frac{8\times7}{2} = 28$。

一个图所有顶点度数之和为 $30$,边数是多少?

$2|E| = 30 \Rightarrow |E| = 15$。

存在一个图,五个顶点的度数恰为 $1,2,3,4,5$。

度数和 $1+2+3+4+5=15$ 为奇数,不可能等于 $2|E|$,故不存在。

度数为 $2,2,2,2,3,3$ 的连通图可以一笔画。

恰有 $2$ 个奇点,满足欧拉路径条件,可一笔画(以两奇点为起终点)。

$6$ 个人两两握手,但其中没有人和自己握手,每人恰好与 $4$ 人握手,共握手多少次?

度数和 $6\times4 = 24 = 2\times$握手次数,故握手 $12$ 次。

$8\times8$ 棋盘上,两两不在同一行同一列的"车"最多放几个?

每行至多 $1$ 个,共 $8$ 行;对角线构造可达,故最多 $8$ 个。

柯尼斯堡七桥无法一笔走完,根本原因是?

四块陆地度数均为奇数,奇点有 $4$ 个,超过 $2$,故不能一笔画。

要证明"最多能放 $N$ 个",完整解答应包含?

求最优值需"上界论证 + 达到上界的构造"两步吻合。