6.4 Gallai’s and Berge’s theorems

Suppose $M$ is a maximum matching. Then $S=V-V(M)$ is also an independent set. If there are edges between vertices of $S$, then such edges can be added to $M$ and one can obtain a larger matching. Hence there are no edges between vertices of $S$ and hence it is a independent set. Construct a edge cover as follows : Add all edges in $M$ to $Q$ and for each $v\in S$, add one of its adjacent edges to $Q$. Since there are no isolated vertices, $v$ has atleast one adjacent edge. Thus $|Q|=|M|+|S|$ and since $V(M)\bigsqcup S=V$, we can derive that

Let $Q$ be a minimum edge cover. Then $Q$ cannot contain a path of length more than $2$. Else, by removing the middle edge in a path of length at least 3, we can obtain a smaller edge cover. By the previous exercise, $Q$ is a graph consisting of star components. If $C_1,\mathrm{\dots },C_k$ are the components of $Q$, then $V(C_1)\cup \mathrm{\dots }\cup V(C_k)=V$ and $E(C_1)\cup \mathrm{\dots }\cup E(C_k)=Q$. Now choose a matching $M=\{e_1,\mathrm{\dots },e_k\}$ by selecting one edge from every component $C_1,\mathrm{\dots },C_k$. Since $C_i$’s are disjoint, $M$ is a matching. Thus, using the fact that each $Q$ is a forest with $k$ components, we can derive that

∎

Suppose there is an $M$-augmenting path $P$. Let $P=v_0{v}_1\mathrm{\dots }{v}_k$. Since $P$ is $M$-augmenting, $(v_0,v_1),(v_2,v_3),\mathrm{\dots },(v_{k-1},v_k)\notin M$ and $(v_1,v_2),(v_3,v_4),\mathrm{\dots },(v_{k-2},v_{k-1})\in M$. Now, observe that $M^{\prime }=M-P\cup \{(v_0,v_1),(v_2,v_3),\mathrm{\dots },(v_{k-1},v_k)\}$ is a larger matching than $M$. Hence if $M$ is a maximum matching, there is no $M$-augmenting path.

Suppose $M^{\prime }$ is a larger matching than $M$. We shall construct an $M$-augmenting path and prove the theorem by contraposition. Let $F=M\mathrm{△}{M}^{\prime }$. We know by the above exercise that the components of $F$ are paths or even cycles. Since $|M^{\prime }|>|M|$, there must be a component of $F$ such that $M^{\prime }$ has more edges in that component than $M^{\prime }$. If a component in $F$ is an even cycle, it consists of same number of edges from $M$ and $M^{\prime }$. Thus, the component for which $M^{\prime }$ has more edges must be a path, say $P=v_0\mathrm{\dots },v_k$. Since $P\subset F$, we have that $P$ has to be an $M$-alternating path i.e., $(v_0,v_1)\in M^{\prime },(v_1,v_2)\in M,\mathrm{\dots }$ or $(v_0,v_1)\in M,(v_1,v_2)\in M^{\prime },\mathrm{\dots }$. Since $m^{\prime }:=|M^{\prime }\cap P|>|M\cap P|=m$ and that $P$ is an $M$-alternating path, we derive that $m^{\prime }-m=1$ and $k=2m+1$. Further, this implies that $(v_0,v_1),(v_2,v_3),\mathrm{\dots },(v_{k-1},v_k)\in M^{\prime }$ and $(v_1,v_2),(v_3,v_4),\mathrm{\dots },(v_{k-2},v_{k-1})\in M$ i.e., $P$ is an $M$-alternating path. If $v_0\in V(M)$ then there exists $(w,v_0)\in M$ for some $w\ne v_1$. Also $(w,v_0)\in M\setminus M^{\prime }\subset F$ contradicting the assumption that $P$ is not a component. So $v_0\notin M$ and similarly $v_k\notin M$. Thus, we have that $P$ is an $M$-augmenting path as needed. ∎