Páros gráfok
Akkor nevezunk egy G gráfot párosnak, ha G csucsainak halmazát fel tudjuk ugy osztani egy A és B halmazra, hogy az osszes G-beli élre teljesul hogy az egyik végpontja A-ban van, a másik pedig B-ben. Egy G páros gráfot kovetkezoképpen jelolunk: G = (A,B).
Teljes páros gráfnak nevezunk egy olyan páros gráfot melyben minden A-beli pont ossze van kotve minden B-beli ponttal. Jelolés: Ka,b, ahol a = | A | és b = | B | .
Tétel
Egy G gráf akkor és csak akkor páros, ha minden G-beli kor páros hosszuságu.
Bizonyitas:
Az elso irány nyilvánvalo, ugyanis ha C egy kor a G páros gráfban, akkor C pontjai alternálnak A és B kozott. Tehát világos hogy C-nek páros sok csucsa van.
A másik irányhoz megmutatjuk, hogy ha G minden kore páros sok pontbol áll, akkor meg tudunk adni megfelelo A és B halmazokat. Tekintsunk egy tetszoleges x pontot a gráfban. Ezt rakjuk A-ba. Most, x minden szomszédját rakjuk B-be, és az osszes olyan B-beli pont szomszédját amelyet még nem helyeztunk el, rakjuk A-ba. Ezt folytassuk amig minden pontot el nem helyeztunk A-ba vagy B-be. Ez az algoritmus azért lesz jo, mert ha egy halmazban lenne két szomszédos csucs, akkor a gráfban lenne páratlan kor is, ez viszont ellentmondas.
