Bevezetés a számításelméletbe 1. gyakorlat
13. feladatsor (2002. máj. 17.)

1. Vizsgáljuk a következő játékot. Adott $n$ darab pont, kezdetben semelyik kettő nincs összekötve. A két játékos felváltva lép. A soron következő az $n$ pont közül tetszőlegesen kiválasztott kettő közé behúz egy élet. Az veszít, aki olyan élet húz be, melytől kör keletkezik a gráfban. Melyik játékosnak van nyerő stratégiája? (Vizsga, 2001. jan.)
2. 1. Rajzolj olyan 2, 3, illetve 4 csúcsú gráfot, amely izomorf a duálisával!
   2. Van-e minden $n$-re olyan $n$ csúcsú gráf, amely izomorf a duálisával?
3. Keress gyengén izomorfakat az alábbi gráfok között!
   $\left(\textup{a}\right)$ $\ \left(\textup{b}\right)$ $\ \left(\textup{c}\right)$ $\ \left(\textup{d}\right)$ $\ \left(\textup{e}\right)$
4. 1. Rajzoltam egy nyolc csúcsú fát. Mi lehet a duálisa?
   2. Bizonyítsd be, hogy tetszőleges két $n$ csúcsú fa gyengén izomorf egymással!
5. Van-e olyan egyszerű, síkbarajzolható gráf, amelynek
   1. kétszer annyi
   2. fele annyi
   csúcsa van, mint a duálisának?
6. Egy 20 csúcsú konvex poliéder lapjainak száma 12. Hány oldala van az egyes lapoknak, ha tudjuk, hogy ez a szám minden lapra azonos? (Vizsga, 1999. febr.) Melyik ez a poliéder?