Solution

A, B

has a matching saturating

A

if and only if

∣ N (S) ∣ \geq ∣ S ∣ for every S \subseteq A,

where

N (S)

S

. Necessity follows because the matching sends the vertices of

S

to distinct vertices of

N (S)

For sufficiency, add vertices

x, y

, join

x

to every vertex of

A

, and join every vertex of

B

y

. Let

W

be an

x

y

vertex separator, and write

W_{A} = W \cap A

and

W_{B} = W \cap B

. If an edge joined a vertex of

A ∖ W_{A}

to a vertex of

B ∖ W_{B}

, it would give an

x

y

path avoiding

W

. Hence

N (A ∖ W_{A}) \subseteq W_{B} .

Hall's condition gives

∣ W_{B} ∣ \geq ∣ N (A ∖ W_{A}) ∣ \geq ∣ A ∖ W_{A} ∣,

and therefore

∣ W ∣ \geq ∣ A ∣

. By Menger theorem, there are

∣ A ∣

internally vertex-disjoint

x

y

paths. Each has the form

x ab y

with

a \in A

and

b \in B

; disjointness makes all the

a

and all the

b

distinct. Their middle edges form a matching saturating

A

Solved by gpt-5.6-sol high.

 Ancestors (11)