二分图详解

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 什么样的图是二分图

一个图称为二分图，是指它的顶点可以分成两组，使每条边都从一组连到另一组，没有任何边留在同一组内。这两组称为图的两侧或两部分，而这种划分本身称为一个二分划分。

用符号表示，图 G = (V, E) 是二分图，当且仅当存在不相交的集合 U 和 W，满足 U ∪ W = V，使得每条边都有一个端点在 U 中，另一个端点在 W中。许多教材把图写成 G = (U, W, E)，以便随时看清这种划分。并不要求两侧之间所有可能的边都存在，也不要求两侧大小相同。唯一的规则是一条禁令： U 内部没有边， W内部也没有边。按照顶点与边指南中的说法，两侧都是独立集。

这个性质很容易表述，却出奇地容易被忽略。下图左侧的图是贯穿全文的示例：八个顶点，九条边。画成一个带一条弦的环时，它看起来没什么特别。把同样的顶点排成两列，结构就一目了然。

边表很短，完全可以记在脑子里：

V = {A, B, C, D, E, F, G, H}
E = {AB, AD, AF, BC, CF, DE, EH, FG, GH}          9 条边

U = {A, C, E, G}      W = {B, D, F, H}             每条边都连接 U 与 W

有两个特殊情况值得一开始就说清楚。一条自环把一个顶点连到它自己，所以它的两个端点在同一侧，带自环的图永远不是二分图。平行边不会改变任何事情： u 和 v 之间的第二条边与第一条边一样跨越两侧。这正是简单图与多重图指南中列出的、不受重数影响的性质之一。对于有向图，问题针对其底层无向图提出，因为定义从不关心边指向哪个方向。

2. 两种颜色，一个二分划分

把 U 的顶点涂成蓝色，把 W 的顶点涂成橙色。这样，定义就是说每条边的两个端点颜色不同，而这恰好是一种使用两种颜色的正常着色。两种描述可以互换：

一个图是二分图，当且仅当它可以用两种颜色正常着色。此时它的色数至多为 2：只要至少有一条边就恰好为 2，没有边则为 1。

着色视角揭示了集合视角所隐藏的一个事实。在连通的二分图中，二分划分是唯一的（两侧名称互换不算不同）。把任意一个顶点涂成蓝色，其余顶点就全被确定了：邻居必须是橙色，邻居的邻居是蓝色，一般地，一个顶点为蓝色当且仅当它到起点的距离为偶数。任何地方都没有选择余地。在本文示例中， {A, C, E, G} 与 {B, D, F, H} 是唯一可能的划分。

有多个连通分量的图则不同，因为每个分量都可以单独翻转。有 k 个连通分量时，共有 2k 种正常二着色和 2k−1 种不同的二分划分（每个孤立顶点都算作一个分量）。因此，“顶点 v 在哪一侧？”这个问题在一个分量内部有意义，跨分量则是任意的。如果代码为每个顶点存储一个全局的侧，然后在互不连通的部分之间比较侧，它比较的是彼此独立选定的标签。

3. 你已经见过的二分图

二分图并不是藏在后面某一章的专题。若干最常见的图族都是二分图，其中一些的理由需要稍想一下才能看出。

• 树与森林。树根本没有环，所以不会出任何问题：在任意位置设根，按深度的奇偶给每个顶点着色。每棵树都是二分图，这又是图论中的树一文所阐述结构的一个推论。
• 路径与偶环。路径沿其长度交替着色。顶点数为偶数的环也一样，并且能正确闭合。顶点数为奇数的环则不能，下一节会给出证明。
• 网格与棋盘。把第 r 行第 c 列的格子按 r + c 的奇偶着色，就得到棋盘图案。走到相邻格子会改变奇偶性，所以网格图是二分图。马走一步，一个坐标变 1，另一个变 2，总和为奇数，因此马总是落在相反颜色上，马步图也是二分图。
• 超立方体。立方体图 Qn 以所有 n 位二进制串为顶点，两个串恰好有一位不同时连一条边。翻转一位会使 1 的个数改变一，所以按该个数的奇偶着色即可。
• 凡是由两类事物构成的结构。求职者与职位、用户与商品、作者与论文、学生与课程。当每条边都连接一类与另一类时，图天然就是二分图。

棋盘的例子有一个经典的结论。去掉 8×8 棋盘上两个对角的角格。剩下的 62 格能用 31 块多米诺骨牌铺满吗？每块骨牌覆盖两个相邻格子，各占一种颜色。被去掉的两个角颜色相同，于是棋盘上一种颜色剩 30 格，另一种剩 32 格，因此不可能铺满。用图论的话说，多米诺铺砌就是网格图中的一个完美匹配，而二分图中的完美匹配要求两侧大小相等，这里两侧并不相等。这个谜题由哲学家 Max Black 于 1946 年讨论过，后来经 Martin Gardner 而广为人知；它至今仍是说明二分性值得留意的最精妙论证之一。

同样有用的是那些不是二分图的图。任何含三角形的图都不行，因为三个两两相邻的顶点需要三种颜色。这就排除了所有完全图 Kn，其中 n ≥ 3，也排除了柯尼斯堡七桥：北岸、岛和东岛构成一个三角形。Petersen 图不含任何三角形也不行，因为它到处都是长度为 5 的环。

4. Kőnig 定理：没有奇环

三角形是一种障碍，但不是真正的障碍。真正的障碍是任何长度为奇数的环，而且这是唯一的障碍。

定理。一个图是二分图，当且仅当它不含长度为奇数的环。

这一结果归功于 Dénes Kőnig。Asratian、Denley 和 Häggkvist 将它追溯到他 1916 年发表在 Mathematische Annalen上的论文，带证明的版本见于他 1936 年的著作 Theorie der endlichen und unendlichen Graphen，这是第一本图论教科书（也就是有限图与无限图一文中讨论的那本书）。证明的两个方向都很短，而第二个方向其实是一个伪装起来的算法。

二分图推出没有奇环。沿着环 v0, v1, …, vk−1 走一圈，回到 v0。每一步颜色都会改变，所以 vi 与 v0 同色，当且仅当 i 为偶数。从 vk−1 到 v0 的闭合边连接两种不同颜色，仅当 k − 1 为奇数，也就是仅当环长 k 为偶数。

没有奇环推出二分图。逐个处理连通分量，任选一个根 r。按每个顶点到 r的距离的奇偶性给它着色。假设某条边 uv 连接了两个同色顶点，即 d(u) 与 d(v) 奇偶相同。沿最短路径从 r 走到 u，跨过这条边到 v，再沿最短路径从 v 回到 r。这条闭途径的长度为 d(u) + d(v) + 1，是奇数。

闭途径还不是环，因为它可能重复经过顶点，而粗心的证明恰恰跳过了这一步。一个小引理可以弥补：每条长度为奇数的闭途径都包含一个长度为奇数的环。如果闭途径重复经过某个顶点，就在那里把它拆成两条更短的闭途径；它们的长度之和是奇数，所以其中一条是奇数长，对长度归纳即可完成证明。奇环与假设矛盾，所以这样的边不存在，按距离的着色是正常着色。

图中间的一栏包含值得牢记的陷阱。5 环是无三角形的，却仍然不是二分图。“没有三角形”是必要条件，远不是充分条件。任何奇数长度都算。

本文示例通过了检验。它的环长度为 4（A, B, C, F）、6（A, D, E, H, G, F）和 8（外圈），全是偶数。有两个简单推论值得记住。删除边或顶点永远不会产生奇环，所以二分图的每个子图都是二分图。反之，加上一条边就可能破坏这一性质，下一节会演示。

5. 线性时间的判定

证明的后半部分就是一个过程。从任意顶点开始进行广度优先搜索，给每个新发现的顶点涂上与其父节点相反的颜色，并检查遇到的每条边。只要某条边两端同色，图就不是二分图。如果搜索结束时都没有出现这种情况，这些颜色就是一个有效的二分划分。从未着色的顶点重复这一过程，直到搜完所有连通分量。

好的判定方法不只是回答是或否。它会返回一个证书，可以独立核验：答案为是时给出二着色，答案为否时给出一个实际的奇环。下面的函数两者都能做到。

from collections import deque

def bipartite_or_odd_cycle(graph):
    """对无向图返回 (True, colour) 或 (False, odd_cycle)。"""
    colour, parent, depth = {}, {}, {}
    for start in graph:                      # 每个连通分量，而不只是一个
        if start in colour:
            continue
        colour[start], parent[start], depth[start] = 0, None, 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in colour:          # 树边：给 v 另一种颜色
                    colour[v], parent[v], depth[v] = 1 - colour[u], u, depth[u] + 1
                    queue.append(v)
                elif colour[v] == colour[u]: # 两端同色：奇环
                    return False, odd_cycle(u, v, parent, depth)
    return True, colour

def odd_cycle(u, v, parent, depth):
    # u 和 v 处于相同的 BFS 深度；向上爬直到两条路径汇合。
    left, right = [u], [v]
    while u != v:
        u, v = parent[u], parent[v]
        left.append(u)
        right.append(v)
    return left + right[-2::-1]              # u ... 汇合点 ... v，由边 v-u 闭合

graph = {
    'A': ['B', 'D', 'F'], 'B': ['A', 'C'], 'C': ['B', 'F'], 'D': ['A', 'E'],
    'E': ['D', 'H'], 'F': ['A', 'C', 'G'], 'G': ['F', 'H'], 'H': ['E', 'G'],
}
ok, colour = bipartite_or_odd_cycle(graph)
print(ok, sorted(v for v in colour if colour[v] == 0))
# True ['A', 'C', 'E', 'G']

graph['C'].append('E'); graph['E'].append('C')   # 一条额外的边
print(bipartite_or_odd_cycle(graph))
# (False, ['C', 'B', 'A', 'D', 'E'])

提取环依赖广度优先搜索的一个性质：每条边连接的两个顶点深度之差至多为一。同色的两个顶点深度奇偶相同，所以冲突边连接的两个顶点总是处于相同深度。因此沿父指针同步向上爬，两边会在同一时刻到达汇合顶点。如果两边各爬了 t 步，环就有 2t + 1 条边，按构造必为奇数。

下面是本文示例上的运行过程，然后是加上一条从 C 到 E的边之后：

从 A 开始 BFS     第 0 层：A    第 1 层：B, D, F    第 2 层：C, E, G    第 3 层：H
                  每条边都连接相邻层   → 二分图，颜色 0 = {A, C, E, G}

加入边 C-E        C 和 E 都在第 2 层，所以颜色相同
                  从 C 向上：C, B, A    从 E 向上：E, D, A    在 A 汇合
                  奇环 C, B, A, D, E    5 条边

每个顶点入队一次，每条边被检查两次（两端各一次），所以判定的运行时间为 O(V + E)。这和读入图一样快。深度优先搜索原则上同样可行，但 Python 中的递归 DFS 在长路径上会碰到默认 1,000 的递归上限，这也是迭代式广度优先版本作为更稳妥默认选择的原因之一。

有一个变体值得了解。如果边逐条到达，而你需要在每次插入后知道图是否仍是二分图，重新搜索就太浪费了。一个额外记录每个顶点相对其根的奇偶性的并查集结构，能以每条边近乎常数的均摊时间回答这个问题：只有当两个已共享根的顶点奇偶不同时，才允许把它们连起来。

6. 完全二分图与 n²/4 上限

所谓完全二分图 Km,n，是指一侧有 m 个顶点，另一侧有 n 个顶点，并且包含全部 m × n 条可能的跨侧边。它在二分图中的地位，就如同 Kn 在一般图中的地位：在给定两侧大小时，它是该族中最稠密的成员。

其中两个成员有自己的名字。 K1,n 是星图，即一个中心连接 n 片叶子，它同时也是一棵树。 K3,3 是公用事业图，出自一个古老的谜题：要求把三栋房子与三种公用设施相连，且所有线路互不交叉。这个谜题无解：Kuratowski 1930 年的定理指出，一个图是平面图，当且仅当它不含 K5 或 K3,3的细分，而 K3,3 正是两个禁止结构之一。

二分性给出了一个一行证明，说明 K3,3 不是平面图。在无交叉的画法中，每个面都由一条闭途径围成。二分图没有三角形，所以在至少有三个顶点的简单连通平面二分图中，每个面的边界至少有 4 条边。把所有面边界加起来，每条边恰好被计算两次，于是得到 4f ≤ 2m。代入欧拉公式 v − m + f = 2 得到

m ≤ 2v − 4        适用于 v ≥ 3 的简单连通平面二分图

K3,3:   v = 6,  m = 9,  但 2v − 4 = 8        所以不存在平面画法

第二个经典上界与稠密度有关。如果一侧有 k 个顶点，另一侧有 n − k个，那么边数至多为 k(n − k)，当两侧尽量相等时这个乘积最大。因此一个有 n 个顶点的二分图至多有 ⌊n²/4⌋ 条边，由 K⌊n/2⌋,⌈n/2⌉达到。Mantel 在 1907 年证明，同样的上限对所有无三角形图都成立，并且平衡的完全二分图是唯一达到它的图。这与第 4 节的陷阱形成了有趣的对照：无三角形图不一定是二分图，但最稠密的无三角形图一定是。本文示例有 9 条边，上限为 16，即 K4,4的边数。

度数服从握手引理的一个更精细的版本。每条边在每一侧恰好有一个端点，所以

∑ deg(u)（u 属于 U）  =  |E|  =  ∑ deg(w)（w 属于 W）

示例：     3 + 2 + 2 + 2  =  9  =  2 + 2 + 3 + 2

一个快速推论：如果每个顶点的度数都相同，为 k ≥ 1，那么 k|U| = k|W|，所以正则二分图的两侧大小总是相等。这是通往下一节匹配结果的第一步。

7. 匹配：二分图为何重要

一个匹配是一组边，其中任意两条都不共享顶点。在二分图中，它就是一种分配：每个求职者至多得到一个职位，每个职位至多分给一个求职者。若一个匹配覆盖所有顶点，则称它是完美的。二分图之所以占满教科书，主要是因为其上的匹配问题既重要又能高效求解，而且理论还附带精确的证书。

第一个证书说明何时一侧的所有人都能得到服务。

Hall 定理（1935）。二分图 G = (U, W, E) 存在一个覆盖 U 中所有顶点的匹配，当且仅当每个子集 S ⊆ U 都至少有 |S| 个邻居在 W中。

请仔细阅读这个前提，因为它经常被误引。Hall 条件讲的是覆盖一侧，而不是完美匹配。只有当 |U| = |W|时两者才一致。必要性显而易见：如果两个求职者都只胜任同一个职位，那么他们不可能都被安排。Hall 的贡献在于，这种局部短缺是唯一可能出错的地方。Kőnig 在 1916 年证明了一个推论：每个 k-正则二分图（其中 k ≥ 1）都有完美匹配。

第二个证书证明一个匹配无法再改进。所谓顶点覆盖，是指一组触及每条边的顶点。匹配中的每条边都需要自己的覆盖顶点，所以任何匹配都不大于任何覆盖。在二分图中两者相遇：

Kőnig–Egerváry 定理（1931）。在二分图中，最大匹配的大小等于最小顶点覆盖的大小。

离开二分图，这一点马上就会失效：三角形的最大匹配大小为 1，而最小顶点覆盖大小为 2。在本文示例中存在大小为 4 的匹配，而 {A, C, E, G} 是大小为 4 的顶点覆盖，所以两者无需任何搜索就互相证明了对方最优。

寻找最大匹配要用增广路径：从一个未匹配顶点出发，在匹配外与匹配内的边之间交替，最后到达另一个未匹配顶点的路径。沿路径交换两类边，匹配就增大一。Berge 在 1957 年证明，一个匹配是最大匹配，当且仅当不存在增广路径。在二分图中，寻找增广路径就是一次普通的深度优先搜索，由此得到常被称为 Kuhn 算法的简短方法：

def max_matching(left, adj):
    """Kuhn 增广路径算法。adj 把每个左侧顶点映射到它的右侧邻居。"""
    match_of = {}                            # 右侧顶点 -> 左侧顶点

    def augment(u, seen):
        for v in adj[u]:
            if v in seen:
                continue
            seen.add(v)
            # v 空闲，或者它的配对可以改配到另一个右侧顶点
            if v not in match_of or augment(match_of[v], seen):
                match_of[v] = u
                return True
        return False

    size = sum(augment(u, set()) for u in left)
    return size, {u: v for v, u in match_of.items()}

adj = {'A': ['B', 'D', 'F'], 'C': ['B', 'F'], 'E': ['D', 'H'], 'G': ['F', 'H']}
size, pairs = max_matching(['A', 'C', 'E', 'G'], adj)
print(size, dict(sorted(pairs.items())))
# 4 {'A': 'D', 'C': 'B', 'E': 'H', 'G': 'F'}

结果是一个完美匹配： A–D、 C–B、 E–H、 G–F。它不是唯一的：这个图恰好有三个完美匹配。该方法的运行时间为 O(V · E)，而且和 Python 中任何递归搜索一样，对很深的图需要改写成迭代形式。对于大型实例，标准选择是 1973 年的 Hopcroft–Karp 算法，它每个阶段找到许多条最短增广路径，运行时间为 O(E √V)。

有三个相关问题值得记住名字：

• 带权分配。当每条边都有成本，而你想要最便宜的完美匹配时，Kuhn（1955）的匈牙利算法能高效求解。工作分配指南把它应用于真实的人员安排决策。
• 把匹配看作流。添加一个源点连向 U中的每个顶点，再添加一个汇点，让 W中的每个顶点连向它，每条边容量设为 1，那么最大流就是最大匹配。Kőnig–Egerváry 定理于是成为最大流等于最小割的一个特例。
• 稳定匹配。当双方彼此排序时，Gale 和 Shapley（1962）证明总存在一个不含任何“双方都更愿意在一起”的配对的匹配，并给出了找到它的算法。

8. 边着色与课程表

给图的边着色，使共享端点的边颜色不同，至少需要 Δ 种颜色，其中 Δ 是最大度，因为度数最大的顶点上的边彼此都冲突。对一般图来说这并不总是够：三角形的 Δ = 2，却需要 3 种颜色，Vizing 在 1964 年证明，对简单图 Δ + 1 种颜色总是足够。二分图从来不需要那种额外的颜色。

Kőnig 边着色定理（1916）。每个二分图（包括多重图）的边都可以恰好用 Δ 种颜色着色。

一种理解方式要用到 Hall 定理：二分图可以通过添加额外的顶点和边补成一个 Δ-正则二分多重图，它进而分解为 Δ 个完美匹配，每种颜色一个。本文示例的 Δ = 3，出现在顶点 A 和 F处，三种颜色就够了。

这正是学校课程表背后的定理。把教师放在一侧，班级放在另一侧，教师每周给某个班上的每节课画一条边，同一位教师多次给同一个班上课时就画平行边。一种颜色代表一个课时，一个正常边着色就是一张没有任何教师或班级同时出现在两处的课程表。Kőnig 定理说明，所需课时数等于任何单个教师或班级的最大周课时量，绝不会更多。真实的课程表还要加入教室和偏好，这会破坏干净的二分结构，问题也正是从这里变难的，但分配的核心仍是一个二分边着色。

9. 矩阵视角

先列出 U 的顶点，再列出 W 的顶点，二分图的邻接矩阵就分成若干块。两个对角块都是零，因为同一侧内部没有边：

A  =  [ 0    B ]            B 是 |U| × |W| 的双邻接矩阵
      [ Bᵀ   0 ]

示例中的 B             B  D  F  H
                   A [ 1  1  1  0 ]
                   C [ 1  0  1  0 ]
                   E [ 0  1  0  1 ]
                   G [ 0  0  1  1 ]

非对角块 B，即双邻接矩阵，包含全部信息，所以程序只存储它。用户与商品的评分表正是一个带权双邻接矩阵，这也是推荐系统天然是图问题的原因；各种存储格式之间的权衡见图的表示。

这种分块结构在特征值上留下了印记。如果一个向量 (x, y)（按两侧拆分）满足 A(x, y) = λ(x, y)，那么 (x, −y) 在把特征值换成 −λ后满足同一方程。因此二分图的谱关于零对称，反之亦然：邻接谱关于零对称的图一定是二分图。本文示例的特征值为 ±2.356、 ±1.477、 ±1.095 和 ±0.262，两两完美配对。加上从 C 到 E 的边，配对就被打破，最大特征值为 2.592，最小为 −2.281。对于连通图，一个数就能判定：图是二分图，当且仅当其最大特征值的相反数也是特征值。例如 5 环有特征值 2，却没有 −2。

化学家在图论学者命名它之前就发现了这一点。1940 年，Coulson 和 Rushbrooke 证明，对于交替烃，即碳原子分成两组且只在两组之间成键的分子，π 电子的能级成对出现，并关于中点对称分布。这个配对定理正是二分图谱对称性在分子上的表述。特征值与结构之间更广泛的联系是谱图理论的主题。

10. 二分图出现在哪里

只要一个系统把两类不同对象联系起来，并且从不直接联系同类对象，二分图就是如实的模型。

有两行值得细看。在编码理论中，Tanner 于 1981 年引入了如今以他命名的图，一侧是码位，另一侧是奇偶校验。Wi-Fi 和 5G 中使用的现代低密度奇偶校验（LDPC）码，正是通过沿这个二分图的边来回传递消息来译码的。而任何超图（其中一条边可以连接两个以上的顶点）都可以无损地存成一个二分关联图，从而可以在上面运行普通的图算法。

合作网络这一行暗藏一个常见的建模错误。分析人员常常把二分图投影到一侧，只要两位作者有共同论文就把他们连起来。投影会丢失信息。三位作者合写一篇论文，与三位作者两两合写三篇不同的论文，在投影中得到的是同一个三角形，尽管背后的合作关系完全不同。请把二分图作为事实来源，只针对具体问题才做投影。

11. 易于判定，难以修复

二分性恰好位于易问题与难问题的边界上，值得看清分界线究竟在哪里。

• 两种颜色：线性时间。第 5 节在 O(V + E)时间内解决了它。
• 三种颜色：NP 完全。判断一个图能否用三种颜色正常着色，是 Garey 和 Johnson 收录的经典 NP 完全问题之一。多一种颜色，就把一次广度优先搜索变成了一个没有已知多项式算法的问题，正如图着色指南所解释的。
• 修复非二分图：NP 难。删除最少的边使图成为二分图，等价于保留最多跨越某个顶点划分的边，这就是最大割问题，Karp 1972 年 21 个 NP 完全问题之一。删除最少的顶点（奇环横贯问题）同样是 NP 难的。

所以判定返回的奇环找起来很便宜，却无法告诉你消除所有奇环的最便宜方式。在加了额外边的本文示例中，删除 C–E 就能恢复二分性，但在一个有许多相互交织奇环的大图上，最小修复确实很难计算。

12. 常见错误

13. 术语表

15. 参考文献

以上定义、定理和归属均出自以下文献，按时间顺序排列。

1. Mantel, W. (1907). "Problem 28." Wiskundige Opgaven 10，60 至 61 页。无三角形图的 ⌊n²/4⌋ 上界。
2. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77(4)，453 至 465 页。二分图的边着色定理，以及正则二分图中的完美匹配。
3. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15，271 至 283 页。平面性与禁止图 K5 和 K3,3。
4. Egerváry, J. (1931). "Matrixok kombinatorius tulajdonságairól." Matematikai és Fizikai Lapok 38，16 至 28 页。
5. Kőnig, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38，116 至 119 页。与 Egerváry 一起给出最大匹配与最小顶点覆盖相等。
6. Hall, P. (1935). "On Representatives of Subsets." Journal of the London Mathematical Society 10(1)，26 至 30 页。
7. Kőnig, D. (1936). Theorie der endlichen und unendlichen Graphen. 莱比锡：Akademische Verlagsgesellschaft。第一本图论教科书，含奇环刻画。
8. Coulson, C. A. and Rushbrooke, G. S. (1940). "Note on the Method of Molecular Orbitals." Proceedings of the Cambridge Philosophical Society 36(2)，193 至 200 页。交替烃的配对定理。
9. Kuhn, H. W. (1955). "The Hungarian Method for the Assignment Problem." Naval Research Logistics Quarterly 2，83 至 97 页。
10. Berge, C. (1957). "Two Theorems in Graph Theory." Proceedings of the National Academy of Sciences 43(9)，842 至 844 页。增广路径刻画最大匹配。
11. Gale, D. and Shapley, L. S. (1962). "College Admissions and the Stability of Marriage." American Mathematical Monthly 69(1)，9 至 15 页。
12. Vizing, V. G. (1964). "On an Estimate of the Chromatic Class of a p-Graph." Diskretnyi Analiz 3，25 至 30 页。
13. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations，85 至 103 页。纽约：Plenum。最大割位列 21 个 NP 完全问题之中。
14. Hopcroft, J. E. and Karp, R. M. (1973). "An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs." SIAM Journal on Computing 2(4)，225 至 231 页。
15. Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. 旧金山：W. H. Freeman。图的 3 着色作为 NP 完全问题。
16. Cvetković, D. M., Doob, M. and Sachs, H. (1980). Spectra of Graphs: Theory and Application. 纽约：Academic Press。对称谱刻画二分图。
17. Tanner, R. M. (1981). "A Recursive Approach to Low Complexity Codes." IEEE Transactions on Information Theory 27(5)，533 至 547 页。
18. Asratian, A. S., Denley, T. M. J. and Häggkvist, R. (1998). Bipartite Graphs and Their Applications. Cambridge Tracts in Mathematics 131。剑桥：Cambridge University Press。奇环定理归于 1916 年这一说法的出处。
19. Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。