图论求证：存在饱和图G中任意匹配M的所有M-饱和顶点的最大匹配

Hey there! Let’s work through this graph theory proof step by step—you’re already halfway there with the right setup (focusing on non-maximal maximal matchings, leaning into contradiction), so let’s unstick that stuck part.

Quick Recap to Align #

First, let’s ground ourselves with clear definitions and goals:

• We’re working with a graph ( G ) with no isolated vertices (you noted this for your prior proof, and it’s critical here too).
• Our target: For any matching ( M ) in ( G ), show there exists a maximum matching ( M^* ) that saturates every M-saturated vertex (i.e., every vertex covered by ( M ) is also covered by ( M^* )).
• As you pointed out, we only need to prove this for non-maximal maximal matchings ( M ): if ( M ) is already maximum, it trivially satisfies the condition (it saturates its own vertices).

Walking Through the Contradiction Setup #

Suppose for contradiction that there exists a non-maximal maximal matching ( M ) such that every maximum matching ( M' ) fails to saturate at least one M-saturated vertex. Let’s pick one such maximum matching ( M' ), and define:

• U = { v ∈ V(G) | v is M-saturated but M'-unsaturated }
  By our assumption, ( U \neq \emptyset )—there’s at least one vertex ( M ) covers that ( M' ) doesn’t.

Since ( M ) is a matching, every vertex in ( U ) has exactly one neighbor paired with it in ( M ). Let’s call the set of these neighbors V = { w_v | (v, w_v) ∈ M, v ∈ U }.

Key Observations About ( V ) #

First, every vertex in ( V ) must be saturated by ( M' ). Why? If any ( w \in V ) was M'-unsaturated, then the edge ( (v, w) ) from ( M ) connects two vertices that ( M' ) misses. We could add this edge to ( M' ) to make a larger matching, which contradicts ( M' ) being maximum. So every ( w \in V ) has exactly one partner in ( M' )—let’s call this partner ( f(w) ).

Traversing Alternating Paths to Break the Contradiction #

Now let’s look at what ( f(w) ) can be, and how we can adjust ( M' ) to cover more M-saturated vertices:

1. Case 1: ( f(w) ) is M-unsaturated
   Consider the short alternating path: ( v \rightarrow w \rightarrow f(w) ) (switching between an M-edge and an M'-edge). We can build a new maximum matching ( M'' = (M' \setminus {(w, f(w))}) \cup {(v, w)} ). This matching is the same size as ( M' ) (so it’s still maximum), but now ( v \in U ) is saturated by ( M'' ). The set of M-saturated but M''-unsaturated vertices is now ( U \setminus {v} )—smaller than before.

2. Case 2: ( f(w) ) is M-saturated

   • If ( f(w) \in U ), we’ve formed an alternating cycle: ( v \rightarrow w \rightarrow f(w) \rightarrow w_{f(w)} \rightarrow \dots \rightarrow v ) (alternating M and M' edges). We can swap the edges in this cycle: ( M'' = (M' \setminus \text{cycle } M'\text{-edges}) \cup \text{cycle } M\text{-edges} ). This ( M'' ) is still maximum, and it saturates all vertices in the cycle—including ( v ), so again ( U ) shrinks.
   • If ( f(w) \notin U ), then ( f(w) ) is both M-saturated and M'-saturated (since it’s not in ( U )). We can keep extending this alternating path: ( v \rightarrow w \rightarrow f(w) \rightarrow x ) (where ( x ) is ( f(w) )’s partner in ( M )), then ( x )’s partner in ( M' ), and so on. Since ( G ) has finite vertices, this path must either:
     • Loop into a cycle (which we already handled, leading to a smaller ( U )), or
     • End at a M'-unsaturated vertex ( u ). But ( u ) has to be M-unsaturated (if it were M-saturated, it would be in ( U ) or M'-saturated—contradiction). Wait a second: this path would be an augmenting path for ( M' ) (starts and ends at M'-unsaturated vertices, alternates edges), which violates Berge’s theorem (maximum matchings have no augmenting paths). That’s a direct contradiction!

Wrapping Up #

In every scenario, either we can construct a maximum matching that covers more M-saturated vertices than ( M' ), or we hit a contradiction (like an augmenting path for a supposed maximum matching). Since ( U ) is finite, repeating this process will eventually give us a maximum matching that saturates all vertices in ( U )—meaning every M-saturated vertex is covered.

This contradicts our initial assumption that no such maximum matching exists. So our original claim holds: for any matching ( M ), there exists a maximum matching that saturates all M-saturated vertices.

内容的提问来源于stack exchange，提问作者ping