Min-Max Theorems¶

\(\alpha + \beta = n\)¶

The complement of an independent set is a vertex cover, and the complement of a vertex cover is an independent set (why?). Consequently, if you consider the maximum independent set, its complement is the minimum vertex cover, and vice versa.

\(\alpha^{\prime} + \beta^{\prime} = n\)¶

First, we must assume that the graph has no isolated vertices, because otherwise, an edge cover is not defined for such a graph.

Now, consider a minimum edge cover.

Initially, we can deduce that there are no cycles in this set of edges (because if there were, removing one edge from the cycle would result in a smaller set that is still an edge cover). Therefore, each connected component of it is a tree.

Then, we can deduce that in none of these trees is there a path of length greater than 2 (why?). Therefore, each of these trees is a star.

The number of stars is \(n-\beta^{\prime}\). From each star, exactly one edge can be chosen to form a matching, whose size is less than or equal to the maximum matching. That is, \(n-\beta^{\prime} \leq \alpha^{\prime}\), which implies \(n \leq \alpha^{\prime} + \beta^{\prime}\).

Now consider a maximum matching.

Consider any vertex \(u\) that is not covered by the maximum matching. All neighbors of \(u\) must be covered by the maximum matching (why?), and since we have no isolated vertices, \(u\) has at least one neighbor.

Now we construct an edge cover. First, we add all edges of the matching to it. Then, for each vertex not covered by the maximum matching, we add one of its incident edges to the edge cover. Now we have an edge cover of size \(n - \alpha^{\prime}\) because the initial \(\alpha^{\prime}\) edges each covered two vertices, and the remaining edges each covered one vertex. So, \(n-\alpha^{\prime} \geq \beta^{\prime}\), which implies \(n \geq \alpha^{\prime} + \beta^{\prime}\).

Finally, the two parts above prove the statement.

\(\beta \geq \alpha^{\prime}\)¶

Consider a maximum matching. To cover only the edges belonging to this matching, you need \(\alpha^{\prime}\) vertices. (Each vertex can cover at most one of them). Therefore, \(\beta \geq \alpha^{\prime}\).

\(\alpha^{\prime} = \beta\)¶

From the previous section, we had \(\beta \geq \alpha^{\prime}\), so every vertex cover is greater than or equal to a matching. Therefore, if we find a matching that is equal to a vertex cover, we have proven the statement. Additionally, that matching will be maximum, and that vertex cover will be minimum.

Consider a minimum vertex cover. Suppose our bipartite graph has two partitions \(X,Y\), and our set of vertex cover vertices is \(X1 \cup Y1\), where \(X1\) is from partition \(X\) and \(Y1\) is from partition \(Y\). Also, let \(X2=X-X1, Y2=Y-Y1\).

Now consider the graph containing only the vertices \(X1,Y2\). We want to find a perfect matching from \(X1\) to \(Y2\) (meaning all vertices in \(X1\) are included in the matching).

We check Hall's condition for finding a perfect matching from \(X1\) to \(Y2\). Suppose \(S \subseteq X1\). We claim that \(|S| \leq |n(S)|\) holds. Assume it does not hold, i.e., \(|S| > |n(S)|\). Then, if we remove the set \(S\) from the vertex cover and add the set \(n(S)\) to the vertex cover, all edges are still covered, and we have arrived at a smaller vertex cover, which contradicts the minimality of the current vertex cover. Thus, Hall's condition holds.

Similarly, a perfect matching can be found from \(Y1\) to \(X2\). This implies that we have found a matching whose size is equal to the vertex cover.

\(\beta^{\prime} = \alpha\)¶

From previous sections, we know that \(\alpha^{\prime} = \beta\) and \(n - \alpha = \beta\) and \(n - \beta^{\prime} = \alpha^{\prime}\) hold.

Therefore, \(n - \alpha = n - \beta^{\prime}\), which implies \(\alpha = \beta^{\prime}\).