↑別に難しくなかった
最大フローを流した状態の残余グラフをGとして、GからS->v1->v2->Tに流れているフローを押し戻してv1を消したグラフをG'とする
G'にSからTへの増加パスが存在することが、v1を消しても最大マッチングの大きさが減らない必要十分条件である

G'にSからTへの増加パスPが存在するとする
Pがv2を含まなければPを伝ってSからTに行った後、T->v2->v1->Sと戻ってくるのがG上のサイクルになっている
Pがv2を含んでいる場合はPを伝ってSからv2に行った後v2->v1->Sと戻ってくるのがG上のサイクルになっている
どちらの場合もv1, v2, SはG上で強連結

逆にv1, v2, SがG上で同じ強連結成分に属するとする
v2->v1->SはG上で一方通行のパスだから、Sからv2へのv1を含まないパスが存在して、これにv2->Tを加えるとG'上でSからTへの増加パスである

(v2を消す場合もv1, v2, Tに関して同じことが言える)

この方針なら二部グラフでもO(M sqrt(N)))とかで解けてそう