视频来源：2.7.1 补图_哔哩哔哩_bilibili
目录
1. 补图
1.1. 补图
2. 双图
2.1. 双图定理
3. 图兰定理/托兰定理
4. 极图理论
5. 欧拉图
5.1. 欧拉迹
5.2. 欧拉闭迹
5.3. 欧拉图
5.4. 欧拉定理
5.5. 伪图
1. 补图
1.1. 补图
（1）补图示例：其中G为母图，G'为其补图
（2）定义：设 , 则
的补图
, 其中
（所有顶点关联边二元集不包含
的子集）
（3）推论：和它的补图
有可能同构，即
（4）例题：六个人的团体中，或有三个人互相认识，或有三个人互相不认识。可用图和补图来做。
（5）拉姆齐定理：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识
2. 双图
2.1. 双图定理
（1）只用一刀切开所有边就好了，看边的两边是否在不同子图中。
（2）定理1：双图也称2部图，其中圈的度数一定为偶数（充分必要条件）。
证明：圈可以表示成 ，若
，则
。因此单数顶点都属于
， 偶数顶点都属于
（2）定理2：有 ，
，
，
，
为偶数，则图中一定有圈
3. 图兰定理/托兰定理
（1）定理：设 是一个
图，如其中没有三角形，则
。其中中括号为求整符号
（2）证明：显然，对于p=1,2,3时结论都成立。则分别证明p为奇数（p=2n-1）和偶数（p=2n）的情况；
假设p=2n-1时成立，则需证p=2n+1时成立
设p=2n-1的图G’，p=2n+1的图为G，有G-u-v=G';（u和v为两个顶点，若u,v连接，则它们一定没有公共邻接点，否则构成三角形；若它们不邻接，则可能存在公共邻接点。视频中老师应该是使他们邻接的，这样可以使第一个顶点u的邻接边假设到最大）
知G'是一个(2n-1,q')图，知 ;
（u和v邻接，且无公共邻接点的情况）
4. 极图理论
（1）找到边最多的图，但不含
5. 欧拉图
5.1. 欧拉迹
（1）定义：包含图的每一条边的迹
5.2. 欧拉闭迹
（1）定义：包含图的所有顶点的闭迹
5.3. 欧拉图
（1）定义：包含欧拉闭迹的图称为欧拉图
5.4. 欧拉定理
（1）定理1：G是欧拉图⇔G连通且每个顶点度为偶数
（2）定理2：图中有一条欧拉开迹⇔G中恰有2个奇度顶点
（3）定理3：设G有2n个奇度顶点，则G至少有n条迹
5.5. 伪图
（1）多重图定义：两个顶点可以之间有多条边
（2）带环图定义：存在顶点到自身的边
（3）伪图：包含多重图和带环图
