Vybrané kapitoly z diskrétnej matematiky

1. Ktoré z nasledujúcich grafov sú rovinné grafy?

2. Ukážte, že grafy K₅ a K_3,3 nie sú rovinné. Nakreslite diagramy týchto grafov tak, aby sa čo najmenší počet ich hrán pretínal.

3. Dokážte, že strom je rovinný graf.

4. Je Petersenov graf rovinný?

5. Dokážte, že ak  je rovinný graf s  vrcholmi, tak pre počet hrán platí: . Nakreslite diagram grafu, pre ktorý platí rovnosť.

6. Dokážte, že ak pre všetky stupne vrcholov v_i  platí deg(v_i) = 3  , tak počet všetkých  uholníkových oblastí je rovný číslu .