grapht theory final question 3 candidates

Berge's Theorem-Statement - A matching M in a graph G is a maximum matching if and only if there is no M-augmenting path.

Forward: If there is an augmenting path P, the symmetric difference of M and P creates a larger matching, so M wasn't maximum. Backward: Assume M is not maximum, so a larger matching M' exists. The symmetric difference of M and M' forms alternating paths and cycles. Since |M'| > |M|, at least one component must be a path with more edges from M' than M. This component is exactly an M-augmenting path.

Kőnig's Theorem-Statement - In any bipartite graph, the size of a maximum matching is exactly equal to the size of a minimum vertex cover.

Let M be a max matching. Let U be unmatched vertices in Part A. Let Z be all vertices reachable from U via alternating paths. Define the vertex cover S = (A minus Z) union (B intersect Z). Prove S is a valid cover by showing no edges go from A intersect Z to B minus Z. Finally, show |S| = |M| because every vertex in S is paired with exactly one unique edge from the matching M.

Mendelsohn-Dulmage Theorem-Statement - If a bipartite graph has a matching M1 covering subset A1, and a matching M2 covering subset A2, there exists a matching M covering A1 union A2.

Consider the symmetric difference of M1 and M2. This graph consists of isolated vertices, alternating paths, and cycles. To build the final matching M, go through each component: for cycles and even paths, pick all edges from either M1 or M2. For odd paths, pick the edges from the matching that covers both endpoints. This combination optimally preserves the covered vertices from both matchings, guaranteeing A1 union A2 is covered.

Gale-Shapley Algorithm - An algorithm used to find a stable matching in a bipartite graph with ranked preferences. Process:

To prove a stable matching exists, show the Deferred Acceptance Algorithm works: 1. Termination: Men propose to women they haven't asked before; since total possible proposals are finite (n squared), the process must end. 2. Completeness: Everyone is matched because a man only stays unmatched if he is rejected by all women, but women only reject if they have a better offer. 3. Stability: Assume a blocking edge (m, w) exists. Since m prefers w, he must have proposed to her first. If she is not with him, she rejected him for a better offer. Thus, w prefers her current partner over m, contradicting the definition of a blocking edge.

Thomassen's Theorem Proof (5-Choosability)-Statement: Every planar graph is 5-choosable.

1. Use induction on a stronger claim: a near-triangulation (outer face is a cycle C, inner faces are triangles) is colorable if: two adjacent vertices on C are pre-colored (list size 1), other vertices on C have list size 3, and all internal vertices have list size 5.
2. Base Case: A single triangle satisfies this.
3. Induction Step: Pick a boundary vertex v adjacent to one pre-colored vertex. Find two colors in its list not used by its boundary neighbor.
4. Remove v and reduce the lists of its internal neighbors by those two colors (keeping their list size at least 3).
5. By induction, the smaller graph is colorable.
6. When v is added back, it has at least one color left in its list (3 or 5) that does not conflict with its neighbors.