Egy $G$ gráfot páros gráfnak nevezünk, ha csúcsainak a $V(G)$ halmaza felbontható az $A$ és $B$ diszjunkt részhalmazokra, úgy hogy $A$-n és $B$-n belül nem vezetnek élek.
A páros gráfok kromatikus száma 2, élkromatikus számukra pedig König Dénesnek van egy remek tétele:
Ha $G$ páros gráf, akkor $ \chi_e(G) = \Delta(G) $
Egy gráfot páros gráfnak nevezünk, ha csúcsainak halmaza felbontható két diszjunkt részhalmazra, úgy hogy a két halmazon belül nem vezetnek élek, csak köztük.
a) A $G$ gráf csúcshalmaza legyen a $V(G)=\{ 1, 2, 3, \dots, 30 \}$. Az $x,y \in V(G)$ csúcsok pontosan akkor legyenek szomszédosak $G$-ben, ha $ \mid x -y \mid = 3$ vagy $\mid x -y \mid = 5$. Határozzuk meg a $G$ gráf $\chi{(G)}$ kromatikus számát és $\chi_e{(G)}$ élkromatikus számát.
b) Egy 20 csúcsú fában 11 csúcs foka 1 és a maradék 9 csúcs foka is azonos. Határozzuk meg a fa élkromatikus számát.
c) Egy 1000 csúcsú gráfot úgy kaptunk, hogy vettünk két 500 pontú utat, és az egyik út minden pontját összekötöttük a másik út minden pontjával. Mekkora az így kelektező gráfnak a kromatikus száma és az élkromatikus száma?
d) Egy 1001 csúcsú $G$ gráfot két körből, egy 500 pontú és egy 501 pontú körből készítünk úgy, hogy az egyik kör minden csúcsát összekötjük a másik kör minden csúcsával. Mekkora az így keletkező gráf kromatikus száma és élkromatikus száma?
