5. 定理：入度的和 = 出度的和 = 边数
带有向边的图有许多性质是不依赖于边的方向的。
因此，忽略这些方向经常是有用处的。忽略边的方向后得到的无向图称为基本无向图。带有向边的图与它的基本无向图有相同的边数。
6. 几种特殊的图
6.1 完全图 Kn
完全图：n个顶点的完全图记作Kn，是在每对不同顶点之间都恰有一条边的简单图
非完全图：至少有一对不同的顶点不存在边相连的简单图
含n个顶点的完全图的边数：n · (n - 1)/2，即C2n
为什么K~n~表示完全图呢？ 一些消息来源称，这个符号中的字母K代表德语单词komplett，但完全图的德文名称vollständigerGraph不包含字母K，其他来源则表示符号表示KazimierzKuratowski图论
6.2 圈图 Cn
圈图：圈图Cn（n ≥3 ）是由n个顶点v1，v2，···，vn以及边{v1，v2}，{v2，v3}，···，{vn-1，vn}，{vn，v1}组成的
Cn，C表示circle嘛
含n个顶点的圈图的边数：n
6.3 轮图 Wn
轮图：当给圈图Cn（n ≥3 ），添加另一个顶点，并把这个新顶点与Cn中的n个顶点逐个连接时，就得到轮图Wn
注意，轮图Wn的下标n是轮圈上的顶点数，不是总顶点数（总顶点数是n+1，加上中心的那个顶点）
Wn，W表示wheel（轮）嘛
含n个顶点的轮图的边数：2 ·（n - 1）
6.4 n立方体图 Qn
n立方体图：n立方体图记作Qn，是用顶点表示2n个长度为n 的比特串的图。
注意，两个顶点相邻 iff 它们所表示的比特串恰恰有一位不同。
含n个顶点的n立方体图的边数：2n
7. 二分图
定义：若把简单图G的顶点集分成两个不相交的非空集合V1和 V2， 使得图中的每一条边都连接V1中一个顶点和V2中的一个顶点（因此G中没有一条边会连接V1中两个顶点或V2中两个顶点），则G称为二分图。
当此条件成立时称（V1,V2）为G的顶点集的一个二部划分。
7.1 判断一个图是否为二分图的定理
定理：一个简单图是二分图 iff 能够对图中的每个顶点赋予两种不同的颜色，并使得没有两个相邻的顶点被赋予相同的颜色。
例题：
例1：说明C6是二分图
🔴解：
C6是二分图，因为它的顶点集被分成两个集合V1 = { v1， v3， v5}和V1 = { v2， v4， v6}，C6的每一条边都连接V1中的一个顶点和V2中的一个顶点
例2：说明K3不是二分图
🔴解：
若把K3内顶点集分成两个不相交的集合，则两个集合之一必然包含两个顶点。假如这个图是二分图，那么这两个顶点就不能用边连接，但是在K3中每一个顶点都有边连接到其他每个顶点。
上面这两个例题当然也可以直接用染色法，很容易判断
7.2 完全二分图
完全二分图 Km,n 是顶点集划分成分别含有 m 和 n 个顶点的两个子集的图，并且两个顶点之间有边 iff 一个顶点属于第一个子集，而另一个顶点属于第二个子集。
