离散数学证明技术

图论

迭代法，应用去一边操作，寻找不变量，最后化归到极限状况（无边）。
存在路径：非构造性证明，任取路径，若不满足，寻找其性质对路径进行修改，证明其可修改为满足题设。
（搭配归纳法食用）
eg. 通路存在性定理，路径存在性定理。
仅关于度数的代数关系证明
利用放缩。
存在满足性质的子图：从原图开始，不满足就·修改·（删点，删边）每步保持性质，最后发现不能删空（空图不满足）
补图和连通性证明：一个技巧，取第三个点，第三个在原图和补图中至少一个有关系。
边点连通度证明，删掉割集中的边或者点，以使用归纳假设（先删后加）
eg. 关系
度数，连通度，节点数联合证明：
某种意义上说，度数是边约束和点约束的桥梁。
- 一个关系：一个边分割后的连通分支中度数和小于等于完全图边数+割边数
  eg.矛盾点：超过
- 围长（最大回路长）为4==无注意转换思路。证明的是对顶点数的约束，条件是边，用度数当作桥梁
- 注意证明点/边连通度小于等于，只需构造一个删掉个不连通即可。
- 证明一个东西是连通的，只需要证明删去个还联通就可以了。(或反证反设个可割)
- 边上加点法：证明点边关系，在边中间插入一个点，该点强烈依赖于与之相连的两边，便于证明。
  eg.
- 用块证明，没太明白。
  eg.
扩大路径证明法
关于二部图的证明
- 处理二部图的一个有力工具是生成树，一些路径和回路的奇偶性质在生成树上得以保留。
  eg.
- 注意最大匹配带来的一些良好性质
扩大路径证明法
不断扩展出极大路径，注意极大带来的端点的优良性质。

主要用于证明和回路有关的结论。
eg.
构造法，这个没什么可说的
eg. 欧拉图
常见反证矛盾
- 违背握手定理
树上问题
- 树上用归纳法，常利用删边之后两个连通分支都是树
- 树上的度数问题，一般就用计算，因为树的边数是确定的。
  一些定理和中间命题
是简单图,若则中必含长度至少为的初级回路
是简单图且, 图中一定存在偶圈(即长度为偶数的初级回路)
注意欧拉图里当然也可以有欧拉通路。
PS23
遗留问题23 10.1 11
补充一个额外的，判断一个度序列是否可图化：