На­зо­вем весом вер­ши­ны A сумму чисел на всех вы­хо­дя­щих из нее реб­рах; обо­зна­чим это число через За­ме­тим, что сумма весов всех вер­шин графа ровно в два раза боль­ше суммы чисел на всех его реб­рах. До­ста­точ­но до­ка­зать, что сумма всех весов не мень­ше −20000. Из усло­вия сразу сле­ду­ет, что сумма весов любых двух смеж­ных вер­шин боль­ше или равна 0. Вы­бе­рем в нашем графе мак­си­маль­ное па­ро­со­че­та­ние, пусть в нём за­дей­ство­ва­но k рёбер. Сумма весов всех их вер­шин боль­ше или равна 0. Оста­лось до­ка­зать, что сумма весов осталь­ных вер­шин боль­ше или равна −20000. Пусть S  — мно­же­ство всех этих вер­шин.

Ясно, что все вер­ши­ны S по­пар­но не смеж­ны (иначе мак­си­маль­ное па­ро­со­че­та­ние можно было бы уве­ли­чить). По­это­му сумма их весов равна сумме чисел на всех реб­рах, со­еди­ня­ю­щих мно­же­ство S с вер­ши­на­ми мак­си­маль­но­го па­ро­со­че­та­ния.

Рас­смот­рим одно из ребер UV, вхо­дя­щее в мак­си­маль­ное па­ро­со­че­та­ние. Не­слож­но про­ве­рить, что из вер­шин U и V в мно­же­ство S может вести сум­мар­но не более ребер. Из этого сле­ду­ет, что между вер­ши­на­ми па­ро­со­че­та­ния и мно­же­ством S есть не более

ребер. На каж­дом из них стоит число 1 или −1, по­это­му сумма чисел на этих рёбер не мень­ше, чем −200000, что и тре­бо­ва­лось до­ка­зать.