图论与组合：作业 / 1.3

考虑包含 $u$ 的连通分支 $G'$.

由于 $\sum\limits_{v\in G'}d_{G'}(v)=2e(G')$ 是偶数, 所以 $G'$ 中至少还存在一个度数为奇数的顶点. 又只有两个奇度数顶点.

所以另一个奇度数顶点一定是 $v$. 所以 $u,v$ 必定连通, 故存在 $u,v$-path.

考虑 $u,v$ 的邻居 $N(u),N(v)$.

$|N(u)\cap N(v)|=|N(u)|+|N(v)|-|N(u)\cup N(v)|\geqslant d(u)+d(v)-n(G)$.

而每一个 $u,v$ 的公共邻居都会和 $u,v$ 构成一个三角形.

$P_n$: 路径就是一个二部图, 所以最大边数是 $n-1$.

$C_n$: 类似路径, 当 $n$ 是偶数时, 环是二部图最大边数为 $n$.

$n$ 是奇数时, 由于二部图不存在奇环, 所以至多 $n-1$ 条边, 又 $C_n$ 中含有 $P_n$, 故可以取到 $n-1$ 条边.

$K_n$: 设其中一个部集的大小为 $k$, 则另一个部集的大小为 $n-k$, 由于是完全图, 所以一共有 $k(n-k)$ 条边, 最值就是 $\lfloor\frac{n^2}{4}\rfloor$.

$K_n$ 环的个数: $\frac{(n-1)!}{2}$, 因为是完全图, 所以任意一种长为 $n$ 的排列都可以添一条边构成环, 但由于环不考虑起点和遍历春旭所以数量还要除以 $2n$.

$K_{n,n}$: $\dfrac{(n!)^2}{2n}$. 不妨固定起点是 $1$, 然后在其中一个部集方案数就是 $(n-1)!$, 另一个部集 $n!$, 再考虑遍历顺序 (翻转) 除以 $2$.

• a) $\binom{n}{2}-\binom{a}{2}$, 一个大小为 $a$ 的独立集需要删除 $\binom{a}{2}$ 条边.
• b) $\binom{n-k+1}{2}$, 考虑 $k-1$ 个孤立点最优.
• c) $\binom{n-1}{2}$, 考虑有 1 个孤立点.