Halts aka Marriage Thm
G LV E bipartite graph f LUR
G has a perf matching iff VSEL 1StENGH
is Today prove
Let B
G’t Gif
RA claim
easy
via Max flow min cut
Equiv G has no perf matching IS EL ISI IN I
aY Y
u EV u can reach t in V IA
B f be integral max flow residual graph
A
LA LnA LB LNB
RNA RB CA B is min cut
RnB
similar to proof in Lec 8
min cut
max matching Max flow
S INCLA l if min cut ch
Note
WIS LAI
Prope For any cat CX Y we have
XY Ilylt1121tlcurseE let
VERYI
cap
TY
T v EE leela VERB Ikeglemma Lu
KL implies capCA B 1431 t IRAI
KL also implies 1
RA
2cases_
In Gif Cyr
In Gif
def of B andfact that UEA Lu V has direction u u
1431tlRAIs n IRAIch 1431 1LAI
NLLA E INCLA l e l Lal
PfofKL_
Suppose towards a contradiction 74,4 EE wheela VERB
has direction u v
this means u can reach t via V
But contradicting
is saturated by f
Cs ul and W 4 also saturated
un
u can reach t is via some vertex W E L
only way gTt
w
since LA cannot reach t w must be in 43 cLA wCLB letw
there are two distinct edges in ul wir
that go into v and are saturated
f sends two units of flow into v
fact that cut
contradicting unit capacity
has
I