1. feladat: Egy expedíció n csomagot szeretne n ládába bepakolni. A csomagoló észreveszi, hogy minden ládához taláható olyan csomag, amely belefér. Minden csomag legfeljebb egy ládába nem fér bele. Bizonyítsuk be, hogy a csomagolás megoldható.
1.' feladat: Az elsõ feladat gráfelméleti megfogalmazása.
2. feladat: Adott egy párosgráf két egyenlõ (n elemû) színosztállyal. Minden pont foka legalább n/2. Bizonyítsuk be, hogy van benne teljes párosítás.
3. feladat: Egy gráfban független éleket keresünk mohó algoritmussal: Az élek egy rtögzített sorrendjében az összes élet megvizsgáljuk, hogy egy aktuális párosításhoz hozzáadhatók-e. Ha igen, akkor hozzáadjuk. Ha nem, akkor a következõ vizsgált élet nézzük meg. Az algoritmus outputja az utolsó él vizsgálata utáni aktuális párosítás. Bizonyítsuk be, hogy tetszõleges sorrend esetén az output mérete az optimalis párosítás mérete, illetve annak fele közt van.
4. feladat: Adott egy d-reguláris (a gráf minden csúcsának foka ugyanannyi, d) páros gráf. Bizonyítsuk be, hogy van benne teljes párosítás.
5. feladat: Adott egy d-reguláris páros gráf. Bizonyítsuk be, hogy élei kiszínezhetõk d színnel úgy, hogy összefütó élek különbözõ színt kapjanak.
6. feladat: Adott egy páros gráf, amely maximális foka D. Bizonyítsuk be, hogy élei kiszínezhetõk D színnel úgy, hogy összefutó élek különbözõ színt kapjanak.
7. feladat: Adott egy n-szer n-es duplán sztochasztikus mátrix (a mátris elemei nem negatív számok úgy, hogy minden sor és oszlop összeg 1 legyen. Bizonyítsuk be, hogy kiválaszztható n elem a mátrixból úgy, hogy minden sorból és oszlopból pontosan egy elemet válaszzunk ki és a kiválasztott számok pozitívak legyenek.