最大流最小割定理：对任意网络流即其中的两个不同的点 s,t，s \to t 的最大流等于 s \to t 的最小割。
\textbf{Proof:}
对于任意一个 S 和 \overline{S} 间的割，其中 s \in S，令 s 向 S 中的所有点连一条无限容量的边，\overline{S} 向 t 连一条无限容量的边，则新图的流量为割的大小，因此原图的流量 \le 割的大小，即最大流 \le 任意一个割。
而对于一个最大流，考虑点集 S，初始时只有 s \in S，然后对 x \in S，若 f(x,y) < c(x,y) 或 f(y,x) > 0，则将 y 也加入 S，因为不存在 s \to t 的增广路，因此 t \notin S，因此 (S, \overline{S}) 是一个割。而这个割的大小显然为流的大小，因此有 s \to t 的最大流等于 s \to t 的最小割。
\text{Theorem.2}
若某个网络流的每条边的容量都是正整数，则对这个网络流中任意两个不同的点 s 和 t，s \to t 的最大流也是正整数。
\textbf{Proof:}
显然这个网络流的每个割的到小都是正整数，根据最大流最小割定理，这个网络流的最大流也是正整数。
\text{Theorem.3}
对于源点集 S 和汇点集 T，有 S \to T 的最大流等于 S \to T 的最小割。
\textbf{Proof:}
考虑新建两个点 s 和 t，让 s 向 s_i 连一条容量无限的边，t_i 向 t 连一条容量无限的边，则显然 s \to t 的每个流与 S \to T 的每个流一一对应，且 s \to t 每个有限的割与 S \to T 的每个有限的割一一对应，因此 S \to T 的最大流等于 S \to T 的最小割。
\text{Theorem.4}
考虑对一个只有点有容量的网络流和其中两个点 s,t，其中 s 和 t 的容量无限，则 s \to t 的最大流等于 s \to t 的最小割。
\textbf{Proof:}
考虑将每个点 a 拆成 a_- 和 a_+，a_- 连所有入边，a_+ 连所有出边，并令 a_- 向 a_+ 连一条容量为点的容量的边，那么新图中 s_+ \to t_- 的每个流和割都能与原图 s \to t 的每个流和割一一对应，因此原图 s \to t 的最大流等于最小割。
连通性
定义：对一个无向图 G，称其为连通的，当且仅当任意两个点之间都存在一条路径；称其为 k 连通的，当且仅当 或 |V(G)| > k 且删除任意 k-1 个点后 G 任然连通，对 k 边连通有相似的定义。特殊的，任意一张图都是 0 连通的和 0 边连通的。令 k(G) 为最大的自然数使得 G 为 k(G) 连通的，\lambda(G) 为最大的自然数使得 G 为 \lambda(G) 连通的。
将每条边 (u,v) 变成两条 u \to v 和 v \to u 的有向边，给每个点赋 1 的容量就能根据 \text{Theorem.4} 得到 (1)，给每条边赋 1 的容量就能根据 \text{Theorem.1} 得到 (2)。
\textbf{Proof.2:}
令 k 为最少的删除的点数使得删除若干个非 s,t 的点使得 s,t 不连通，那么显然最多有 k 个 s \to t 的不交路径，而 k \le 1 时结论显然成立，假设结论错误，找到最小的 k 使得有反例，令 G 为 k 的所有反例中边数最少的那个，那么最多有 k-1 条 s \to t 的不交路径。
令 W 为能分开 s,t 的 k 个点的点集，且 s,t 和 W 中的点不全相邻，考虑将 W 删除，并将包含 s 的连通分量替换为 s'，加回 W，并令 s' 连向 W 中的每个点，称新图为 G_s，显然我们仍然至少需要 k 个点去分开 s',t，且 G_s 的边数少于 G，因此 s' \to t 有 k 条不交路径，即存在 W \to t 的不交路径，同理，存在 s \to W 的不交路径，因此存在 k 条 s \to t 的不交路径。
下面证明能找到这样的 W。假设不存在，考虑一条 s \to t 的最短路 s \to x_1 \to x_2 \to \cdots \to x_l \to t，显然不存在点 x 使得 x 同时与 s,t 相邻，否则 G-x 就是一个 k-1 的反例。因此 l \ge 2，考虑 W_0 为 G - x_1 x_2 的一个能分开 s,t 的 k-1 个点的点集，那么由于 x_1 不与 t 相邻，因此 W_1 = W_0 \cup x_1 全与 s 相邻，同理 W_2 = W_0 \cup x_2 全与 t 相邻，因此 W_0 都与 s,t 都相邻，而 |W_0| \ge 1，因此存在点 x 同时与 s,t 相邻，矛盾。
\text{Corollary.6}
对 k \ge 0，一张图 G 是 k 连通的，当且仅当任意两个点间都存在 k 条不交路径，而 G 是 k 边连通的当且仅当任意两个点间都存在 k 条的边不交路径。
类似于多源汇的最大流最小割定理，将门格尔定理推广到起点集 S 和终点集 T，则 S \to T 的不交（包括起点和终点）路径数等于最少的点数，使得删除若干个点后不存在 S \to T 的路径。只要新建两个点 s,t，令 s 向 S 中每个点连边，t 向 T 中每个点连边。
匹配
对集合 X，令集合集 A = \{ A_1, A_2, \dots, A_n \} 满足 \forall i, A_i \subset X，集合 \{ x_1, x_2, \dots, x_n \} 为 A 的独立代表集，当且仅当 \forall i, x_i \in A_i，且 \forall i \ne j, x_i \ne x_j。一个很自然的例子是二分图 G=(V_1, V_2, E)，其中 X = V_2，A_i 为和 i 相邻的点。若存在 A 的独立代表元，则此二分图存在完美匹配。这个可以看作一个婚姻问题，即 n 个男孩和 m 个女孩之间有若干对认识，问最多能成多少对情侣。
\forall S \subset V_1, \sum\limits_{x_i \in S} d_i \le \sum\limits_{j=1}^m \min( | E(S, y_j) |, e_j) + d \textbf{Proof:}
考虑将其转化成一个网络流，点权为 d_i 和 e_j，边权为 1，那么条件变为存在一条流量 \ge \sum\limits_{i=1}^n d_i - d 的流，即所有割都 \ge \sum\limits_{i=1}^n d_i - d。对于一个最小割，显然可以写成 T \cup U \cup E(V_1 - T, V_2 - U)，其中 T \subset V_1, U \subset V_2，当钦定 T 时，对 V_2 的每个点 y_j，如果将其划分进 U，则会有 e_j 的贡献，否则会有 | E(V_1 - T, y_j) | 的贡献，因此枚举 T 的补集 S，就能将条件转化成
\forall S \subset V_1, \sum\limits_{i=1}^n d_i - d \le \sum\limits_{x_i \notin S} d_i + \sum\limits_{j=1}^m \min(e_j, | E(S, y_j) |)
即
\forall S \subset V_1, \sum\limits_{x_i \in S} d_i \le \sum\limits_{j=1}^m \min(e_j, | E(S, y_j) |) + d
\text{Theorem.13}
对有限偏序集 P，定义其链 A = \{ a_1, a_2, \dots, a_m \} 满足 A 中任意两个不同元素都有大小关系，反链 A = \{ a_1, a_2, \dots, a_m \} 满足 A 中任意两个不同元素都没有大小关系。若 P 的最大反链的大小为 m，则 P 由 m 条链组成。
\textbf{Proof:}
考虑用归纳法。假设对所有 |P'| < |P| 都有结论成立，那么令 C 为 P 的最长链，若 P-C 没有大小为 m 的独立集，那么就能直接归纳，否则设 A = \{ a_1, a_2, \dots, a_m \} 为 P_C 的一个反链，而
S^- = \{ x \in P : \exists i, x \le a_i \} S^+ = \{ x \in P : \exists i, x \ge a_i \}
那么 P 中每个元素要么在 S^- 中，要么在 S^+ 中，否则就存在一个大小为 m+1 的反链。进一步的，C 中最小的元素不在 S^+ 中，且 C 中最大的元素不在 S^- 中，否则就能在 C 的开头或末尾添加一个元素了。因此，S^- \ne P, S^+ \ne P，即 |S^-|, |S^+| < |P|。那么设
q(C_i - c \cup S) \ge |S| + 2 |S_0| + 1 + |S| = | S_0 \cup c \cup S | \ge q(G - S_0 \cup c \cup S) = q(G - S_0) - q(C_i) + q(C_i - c \cup S) \ge |S_0| + 1 + |S|
因此
q(G - S_0 \cup c \cup S) = |S_0 \cup c \cup S|
与 S_0 为满足条件的最大的子集的条件不符，所以 C_i - c 存在一个完美匹配。
考虑证明存在 \{ s_i, c_i \} 的完美匹配。设二分图 H = (V_1 = \{ C_1, C_2, \dots, C_m \}, V_2 = S_0, E)，其中 x_i 和 y_j 间有边，当且仅当 G 中存在一条 s_j 到 C_i 中的某个点的边。令 A \subset V_1，设 B = \Gamma_H(A)，那么如果在 G 中将 B 里的点删除，则 A 中的连通块都会独立出来，因此
|A| \le q(G-B) \le |B|
满足霍尔定理，因此存在一个 \{ s_i, c_i \} 的完美匹配。
综上，存在 G 的完美匹配。
\text{Corollary.15}
对于一张图 G=(V,E)，存在一个大小为 n-d 的匹配当且仅当
\forall S \in V, q(G-S) \le |S| + d \textbf{Proof:}
必要性显然，考虑证明充分性。设 W 为一个大小为 d 的完全图，考虑在原图中加入 W，且 W 中的每个点都向 G 中的每个点连一条边，设新图为 G'，令 S' \subset V(G'), S' \ne \varnothing，若 W \not\subset S'，那么 H - S' 连通，因此 q(H - S') \le 1 \le |S'|。否则有 W \subset S'，设 S = S' - W，有
q(G' - S') = q(G - (S' - W)) = q(G-S)
因此
q(G-S) \le |S| + d \Leftrightarrow q(G-S) \le |S'|
所以 G' 有完美匹配，所以 G 有大小为 n-d 的匹配。
稳定婚姻问题
在一个婚姻系统 G=(V_1 = \{ a, b, c, \dots, \}, V_2 = \{ A, B, C, \dots \}, E) 中，有 |V_1| = n 个男人和 |V_2| = n 个女人，他们之间有若干个认识关系。对于每个男人，他对他认识的女人都会有一个偏爱程度的清单，对每个女人同理。现在称一个匹配是稳定的，当且仅当这个匹配是最大匹配，且不存在两个匹配 (a,A) 和 (b,B) 使得 A 比起 a 更喜欢 b，b 比起 B 更喜欢 A（否则 (A,b) 就会私奔）。
令 L(a) 为 a 在所有匹配中能匹配到的点集，要证明的就是在算法中，L(a) 中没有任何一个女人拒绝过 a。假设不是，那么设 a 为第一个被可能的女人拒绝的男人，而 A 是拒绝他的女人，设 A 最后接受了 b。令稳定匹配 M 满足 (a,A) \in M，设 (b,B) \in M，由于 a 是第一个被可能的女人呢拒绝的男人，因此 b 没有被 B 拒绝过，那么有 b 比起 B 更喜欢 A，而 A 比起 a 更喜欢 b，这样 M 就不稳定了。