Minimax Theorems¶

Handshaking Lemma¶

The sum of all vertex degrees in a graph is equal to twice the number of edges:

Proof Suppose we count all edge endpoints. Each edge contributes 2 to the total count, hence \(2|E|\). This must equal the sum of degrees. ∎

 1def calculate_degrees(graph):
 2    # Calculate degree of each vertex
 3    degrees = {}
 4    for v in graph.vertices:  # در اینجا رأس‌های گراف را پیمایش می‌کنیم
 5        degrees[v] = len(graph.neighbors(v))
 6    return degrees
 7
 8# Example usage
 9G = Graph()
10G.add_edges([(1,2), (2,3), (1,3)])
11print(calculate_degrees(G))  # Output: {1: 2, 2: 2, 3: 2}

Euler's Theorem¶

A connected graph contains an Eulerian trail if and only if it has exactly 0 or 2 vertices of odd degree.

The complement of an independent set is a vertex cover, and the complement of a vertex cover is an independent set (Why?). Therefore, if we consider the maximum independent set, its complement will be the minimum vertex cover, and vice versa.

First, we must assume the graph has no isolated vertices, as otherwise an edge cover cannot be defined for such a graph.

Now consider a minimal edge cover.

First, we can conclude this set contains no cycles (if it did, removing one edge from the cycle would yield a smaller set that is still an edge cover). Therefore, each connected component is a tree.

Next, we can conclude none of the trees have a distance greater than 2 (Why?). Hence, each tree is a star.

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

Now consider the maximum matching.

Take any vertex \(u\) not covered by the maximum matching. All neighbors of \(u\) must be covered by the maximum matching (Why?), and since there are no isolated vertices, \(u\) has at least one neighbor.

We construct an edge cover as follows: First, add all edges of the matching to it. Then, for each vertex not covered by the maximum matching, add one of its adjacent 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. Thus \(n-\alpha^{\prime} \geq \beta^{\prime}\), leading to \(n \geq \alpha^{\prime} + \beta^{\prime}\).

Finally, combining the two parts above proves the theorem.

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

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

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

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

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