图杂项

对于任何连通的平面图，$V-E+F=2$。

一个有限图是平面图，当且仅当它不包含 $K_{3,3}$ 或 $K_{5}$ 的细分作为子图，一个图的细分是通过在边上插入若干新的度为 2 的顶点而得到的，也就是说，图中不包含类似 $K_{3,3}$ 或 $K_{5}$ 的结构，即使这些结构被一些中间节点拉长了边。

增量构造：给定无向完全图，边权红蓝二色，找一条从 1 开始的哈密顿路，满足路径要么是先只走红边再只走蓝边，要么是先只走蓝边再只走红边 https://codeforces.com/gym/104030/problem/I

彩绳：给定一棵 $N$ 个节点的树，同时给定 $K$ 条路径，需要选择一些树的边染色，使得每条路径上都有一条染色的边。求最小染色边数。$N \leqslant 10^{5}, K \leqslant 20$。注意到结论 1，在树上随便点 $K$ 个点，构成的树的边数为 $\mathcal{O}(K)$，事实上是 $K - 1$。暴力即可，看上去是 $\mathcal{O}((2^{K})^{2})$ 实际上是 $\mathcal{O}(K \cdot 2^{K})$。https://codeforces.com/contest/1929/problem/E

$N$ 点无向完全图，给每条边标上 $0\sim9$ 的数字，使得图上不存在三元同色环和五元同色环。$N \leqslant 1000$。考虑拆分为 $10$ 个二分图。 着色 - Problem - QOJ.ac