思路：先通过交错路和增广路的概念建立起处理最大匹配的工具，证明匹配最大的充要条件是图中没有增广路。然后证明 Hall 定理，顺便证明了婚配定理，并利用之证明最大匹配与最小点覆盖的对偶性。最后证明最小边覆盖与最大独立集的对偶性，以及这四者之间的关系。
交错路与增广路
对给定的一个匹配$M$，交错路是指由未被浸润的顶点出发，交错经过$\overline M$与$M$中的边的路径，增广路是指起点与终点均未被浸润的交错路。若对一个图$G$与其上的匹配$M$，存在一条增广路$P$，那么$M$与增广路$P$的对称差构成一个边数更大的匹配。
定理：对一个图$G$与其上的匹配$M$，$M$最大当且仅当没有增广路。
必要性显然，现证充分性，即证明没有增广路时$M$一定最大。假设没有增广路且存在更大的匹配$M'$，尝试寻找增广路，从而得到矛盾。
作两匹配的对称差，每个点的度数至多为 2（两个匹配各贡献 1 个），那么对称差的诱导子图的每个分量要么是偶环（二分图没有奇环），要么是链。偶环中属于$M'$的边和属于$M$的边应一样多，因为沿着偶环走，一定是交替经过两匹配中的边（否则同一匹配中有两条边浸润同一顶点）。又由于$|M'|>|M|$，一定有一个分量中属于$M'$的边多于属于$M$的边，这个分量一定是一个交替经过$M'$与$M$的链，从而一定是增广路。得到矛盾。
Hall定理
定理：对一个$X,Y$二部图，存在匹配浸润$X$当且仅当$\forall S\subset X,|N(S)|\ge|S|$，其中$N(S)$是从$S$中的点经过一条边可达的点的集合。
因为$N(S)$一定包含匹配中$S$对应的边，那么显然$|N(S)|\ge|S|$，必要性成立。
下证充分性。假设一个最大匹配$M$没有浸润$X$，即不存在匹配浸润$X$，尝试证明$\exists S\subset X,|N(S)|<|S|$。设$u\in X$没有被浸润，考虑由$u$经交错路可达的点集，记其与$X$的交集为$S$，与$Y$的交集为$T$。若$S=\{u\}$，那么$N(S)=\emptyset,|N(S)|<|S|$，定理成立。现在$S-\{u\}$非空，我们知道$T\subset N(S)$。实际上$T=N(S)$，因为若从$v\in S$出发可达$v'\not\in T$，由于从$u$到$v$的路是交错路，且最后一条边是$M$中的边，那么$vv'$就是$M$之外的边（否则$M$中有两条边浸润$v$），从而$u\rightarrow v\rightarrow v'$构成一个交错路，即$v\in T$，矛盾。所以由$S$中的点经一条边可达的点都在$T$中，即$N(S)\subset T$，故$N(S)=T$。由于$T$与$S-\{u\}$由$M$定义了一个双射，故$|N(S)|=|T|=|S|-1<|S|$，于是我们找到了使得$|N(S)|<|S|$的$S\subset X$，充分性得证。
Hall定理得证后，可以轻松地证明婚配定理：
定理：$k$ -正则的$X,Y$二部图必有完美匹配（$k>0$）。
证：首先，分别根据$X$中的点和$Y$中的点对边进行计数，得$k|X|=k|Y|$，故$|X|=|Y|$，从而浸润$X$得匹配也浸润$Y$，也就是完美匹配。
现证明这样的二部图满足Hall条件，即$\forall S\subset X,|N(S)|\geq|S|$。$\forall S\subset X$，有$m=k|S|$条边与之关联。由于这些边都属于$N(S)$覆盖的边集，所以$m\leq k|N(S)|$，从而$k|S|\leq k|N(S)|$，由$k>0$有$|S|\leq|N(S)|$，Hall条件得到满足。然后由Hall定理即得婚配定理。
最大匹配与最小点覆盖
书上为引入最小点覆盖给出的理由是：对一个匹配，要判定它是否最大需要遍历交错路，很麻烦，需要一个更好找的结构来判定匹配的最大性。这个结构就是最小点覆盖。
定理：最大匹配数$M$与最小点覆盖的顶点数$C$相等。
证明：首先，对一个最大匹配，一个点覆盖必须覆盖这个匹配中的所有边，也就是最小点覆盖的顶点数不少于最大匹配数，$M\leq C$。然后对于任意给定的最小点覆盖，我们尝试寻找一个匹配使得匹配数与最小点覆盖点数相同，从而证明等号必然可以取到。
对$X,Y$二部图上的某个最小点覆盖$V$，我们记$R=V\cap X,T=V\cap Y$。首先$X-R$与$Y-T$中的点不会连边，否则这条边没有被$V$覆盖。然后考察$R$与$Y-T$之间的连边，它们都被$R$覆盖。尝试应用Hall定理证明存在浸润$R$的匹配。对$\forall S\subset R$，如果$|N(S)|<|S|$，那么我们在$V$中将$S$换成$N(S)$，它仍然是点覆盖（因为$S$这些点的作用仅仅是覆盖与$S$相连的边们，而现在$N(S)$可以用更少的点做到这件事），这与$V$的最小性矛盾。所以$R$与$Y-T$的生成子图存在浸润$R$的匹配。同理，$T$与$X-R$的生成子图存在浸润$T$的匹配，并且这两个匹配不相交。于是可以将它们合并为一个原图中的匹配。
现在对于每个最小点覆盖，都可以找到一个匹配使得匹配数与之相等，也就是$M\leq C$中的等号一定可以取到，所以$M=C$。
要解释开头的那个“结构”，就可以理解为：对一个匹配，如果我能在这个匹配上（在每条边上恰选一个点）找到一个点覆盖，那么这个匹配一定最大。这个估计只对肉眼有用吧…
最大独立集与最小边覆盖
感觉这个东西和上节标题听起来就很对偶。
定义：记最大独立集的点数为$\alpha(G)$，最大匹配边数为$\alpha'(G)$，最小点覆盖的点数为$\beta(G)$，最小边覆盖的边数为$\beta'(G)$。
引理：一个点集为独立集，当且仅当其补为点覆盖，故$\alpha(G)+\beta(G)=n(G)$。
证明：若点集为独立集，那么其补必覆盖所有边，否则有边联结独立集中的两点，矛盾。必要性得证。对一个点覆盖，其补集任两点间均无边相连，故其补集为独立集。充分性得证。于是对最小独立集，其补为最大覆盖（否则有更大的覆盖，其补为更小的独立集），从而$\alpha(G)+\beta(G)=n(G)$。
定理：若$G$没有孤立顶点，那么$G$有边覆盖，且$\alpha'(G)+\beta'(G)=n(G)$。
证明：对一个最小边覆盖，尝试构造边数为$n(G)-\beta'(G)$的匹配。若对于最小边覆盖中的某条边，其两个端点都已被其他边覆盖，那么这条边可以去掉，所以不存在这种情况。也就是说，最小边覆盖的诱导子图不含有3-链，它的每个分量都是一个菊花图。记诱导子图的分量数为$k$，那么最小边覆盖中共有$n(G)-k$条边。在每个分量中选取一条边即可得到一个大小为$k$的匹配。这证明了$\alpha'(G)+\beta'(G)\geq n(G)$。
对一个最大匹配，尝试构造一个边数为$n(G)-\alpha'(G)$的边覆盖。只需要对最大匹配没有浸润的每个顶点选择一条边即可，这样得到的边覆盖大小恰为$n(G)-\alpha'(G)$，这证明了$\alpha'(G)+\beta'(G)\leq n(G)$。
综上，$\alpha'(G)+\beta'(G)=n(G)$。
由上节，$\alpha'(G)=\beta(G)$，又$\alpha(G)+\beta(G)=\alpha'(G)+\beta'(G)=n(G)$，于是$\alpha(G)=\beta'(G)$，即最大独立集与最小边覆盖大小相等。