Milyen nem triviális tulajdonságai vannak egy páros gráfnak?

Hirtelen meg nem mondom, mi számít triviális tulajdonságnak, de leírom, amit gráfelméleten megjegyeztem:

-legalább 2 csúcsú fa, erdő, üres gráf mindig páros

-ha egy gráfban minden kör (zárt séta) páros hosszúságú, akkor és csak akkor páros

-K3,3 vagy K5-tel topologikusan izomorf gráfok nem síkbarajzolatók

(és azt hittem többre emlékszem...)

Dehogy nem teljesül az 1-es.

Azért tettük fel azt, hogy legalább 2 csúcsból áll.

Ugye a páros gráf definícója röviden az, hogy van egy A és B nemüres csúcshalmaz, és bármely A-beli csúcsnak csak B-beli szomszédja van.

Tehát a bizonyítás üres gráfra: egy pontot tegyünk A-ba, a többit B-be.

Fára pedig csúcsok számok szerinti indukcióval lehet levezetni.

2-re triviális, az egyik csúcs A-beli, a másik B-beli.

Tegyük fel, hogy n db csúcsra igaz, és n >= 3.

Válasszunk egy egyfokú csúcsot. (mivel legalább 2 ilyen minden fában van)

Ugye, mivel ha hozzáadunk egy fához egy új csúcsot, az mindig első fokú lesz, ezért feltételezhetjük azt, hogy a kiválasztott egyfokú csúcsunk az. Ezt töröljük ki a gráfból, és az egyel kevesebb csúcsú gráfra pedig igaz volt az állítás. Így ha a csúcsunk egyetlen szomszédja A-beli, akkor vegyük őt B-hez, ha B-beli, akkor pedig A-hoz.

Az erdő esete pedig sok fára bomlik le, mindegyik ilyen fát vegyük külön, és alkalmazzuk rá az előzőt.

és bármely B-belinek, csak A-beli csúcsa van.

Ezt lehagytam a definícióból. Az a lényeg, hogy bármely csúcs csak a másik halmazbeli elemekkel lehet szomszédos.