Teorema (Berge, 1957)

Teorema 2.1 (Berge, 1957) Matching M pada graf G akan maksimum jika dan hanya jika G tidak mengandung lintasan M–Augmenting.

Bukti : Asumsikan M merupakan matching pada G. misal G mengandung lintasan M–Augmenting P = v₀v₁, . . . , v_2m+1. Akan dibuktikan M bukan matching maksimum. (perhatikan bahwa _2m+1 jumlah sisi pada P) harus berjumlah ganjil karena setiap sisi lain melewati M, dan v₀v₁ dan v_2mv_2m+1 keduanya tidak melewati M.

Didefinisikan himpunan sisi – sisi M' ⊆E dimana

M' = (M \ { v₁v_2, v₃v_{4, ... ,} v_2m-1v_2m }) ∪{ v₀v_1, v₂v_{3, ... ,} v_2mv_2m+1 }.

Maka, M' merupakan matching pada G dengan nilai │M'│ =│M│+ 1. Karena │M'│ >│M│terbukti M bukan matching maksimum.

Kebalikannya, tentukan bahwa M bukan matching maksimum. Misal M' matching maksimum di G, maka│M'│>│M│ (2.1)

Himpunan H = G[ M ∆ M' ], dengan M ∆ M' menunjukkan beda simetrik di M dan M'.

Setiap simpul di H berderajat 1 atau 2, karena setiap simpul di H insident dengan paling banyak satu sisi di M dan satu sisi di M’. Dengan demikian, komponen H adalah lintasan yang sisi nya bergantian di M dan M’ atau siklus dengan banyak sisi nya adalah genap. Karena M’ dimisalkan sebagai matching maksimum, dari penjelasan sebelumnya diperoleh |M’| > |M|. Akibatnya, H mempunyai lebih banyak sisi di M’ dibandingkan sisi di M. Sehingga lintasan P di H yang sisi awal dan sisi akhirnya adalah anggota dari M’. Dengan kata lain simpul awal serta simpul akhir dari lintasan P merupakan M’–saturated di H, M–unsaturated di G. Maka lintasan P adalah lintasan M–augmenting.