Van itt ez a G(A, B, E) páros gráf.

Ha A-ban és B-ben ugyanannyi csúcs van és létezik A-t fedő párosítás…

akkor az nyilván B-t is fedi, így van a gráfban teljes párosítás.

Ezt a nem túl bonyolult dolgot mondja ki Frobenius tétele.

Frobenius tétele:

A G(A, B, E) páros gráfban akkor és csak akkor létezik teljes párosítás, ha

és

teljesül a Hall-tétel.

Utóbbit akár egy kicsit részletezhetjük is.

Most pedig nézzük, mire is használhatnánk Frobenius tételét, jóra vagy rosszra…

Egy bálon 10 fiú és 10 lány vesz részt. Minden lány legalább 6 fiút ismer és minden fiú is legalább 6 lányt. Az ismertségek kölcsönösek. A nyitótáncon mindenki ismerőssel szeretne táncolni. Bizonyítsuk be, hogy ez lehetséges.

Ugyanannyi lány van, mint fiú, tehát az első feltétel meg is van.

Nézzük, mi a helyzet a másodikkal.

Itt egy hasznos kis trükköt fogunk használni.

Azért nem olyan nagy trükk.

Nézzük először azokat az X halmazokat, amik legfeljebb 6 eleműek.

Mivel X-ben már egyetlen pontnak is legalább 6 szomszédja van, így nyilván

Ezekre az X halmazokra teljesül a Hall-feltétel.

Most nézzük, mi van akkor, ha

Ekkor az A\X halmazban legfeljebb 3 elem van.

De B-ben mindenkinek legalább 6 szomszédja van.

Ez pedig csak úgy jön ki, ha B minden pontjának van szomszédja X-ben.

Vagyis B=N(X).

Ezek szerint N(X) 10 elemű.

Így biztosan teljesül a Hall-feltétel.

Fergeteges nyitótáncra lehet tehát számítani…

Egy 12 csúcsú páros gráfban minden csúcs foka 3 vagy 4. Bizonyítsuk be, hogy van a gráfban teljes párosítás.

Íme, a gráf.

Igazán remek lenne megint a Frobenius tételt használni, ezért azzal kezdjük, hogy igazoljuk: |A|=|B|.

Ha A-ban mondjuk csak 5 pont lenne…

És mindegyik pont foka a lehető legtöbb, vagyis 4…

akkor 20 él indul útnak A-ból.

B-ben ekkor 7 csúcs van, és ha mindegyik foka a lehető legkisebb…

az is 21 darab él.

Hát, ez így nem jön ki.

Még így is kevesebb él indul útnak A-ból, mint amennyinek B-be érkeznie kellene.

A-ban 5-nél több csúcsnak kell lennie…

Na és persze B-ben is.

Ez azt jelenti, hogy mindkét pontosztályban 6 csúcs van.

Eddig jó.

Most nézzük, mi van a szomszédokkal.

Ha X legfeljebb 3 elemű, akkor biztosan teljesül a Hall-feltétel.

Mert X-ben minden pontnak legalább 3 szomszédja van, ezért N(X)-ben is van legalább 3 pont.

Nézzük mi van akkor, ha X-nek 4 eleme van…

B-ben mindenkinek legalább 3 szomszédja van.

Ez pedig csak úgy jön ki, ha B minden pontjának van szomszédja X-ben.

Vagyis ilyenkor B=N(X).

Úgy néz ki, ilyenkor is teljesül a Hall-feltétel.

Ha pedig X 5 vagy 6 elemű, akkor pláne.

Vagyis létezik a gráfban teljes párosítás.