Grafy

Planarność

1. Gdy graf G jest planarny, n oznacza liczb_{}e jego wierzchołków, m liczb_{}e jego kraw_{}edzi, a f liczb_{}e jego ścian licz _{}ac t_{}e nieograniczon _{}a, to n − m + f = 2.

2. Gdy graf G jest planarny, oznaczenia jak poprzednio, n 3 to zachodzi m 3n − 6.

3. Jeśli graf G jest planarny, to zawiera wierzchołek stopnie niewi_{}ekszego niż 5.

4. Jeśli graf G jest planarny, to jego wierzchołki dadz _{}a si_{}e pokolorować na 5 kolorów, tak, by żadne dwa poł _{}aczone kraw_{}edzi _{}a wierzchołki nie były tego samego koloru.

5. Twierdzenie o czterech barwach. Jeśli graf G jest planarny, to jego wierzchołki dadz _{}a si_{}e pokolorować na 4 kolorów, tak, by żadne dwa poł _{}aczone kraw_{}edzi _{}a wierzchołki nie były tego samego koloru (dowód jest trudny, zrobiony dopiero w 1976 roku).

6. K_{5} i K_{3,3} nie s _{}a planarne.

7. Twierdzenie Kuratowskiego. Graf G nie jest planarny wtedy i tylko wtedy, gdy zawiera podgraf homeomorficzny z K_{3,3} lub K_{5}. (grafy G_{1} i G_{2} s _{}a homeomorficzne, jeśli można z nich uzyskać grafy izomorficzne poprzez dostawianie na kraw_{}edziach wierzchołków stopnia 2).

Zadanka

1. Wykaż, że K_{5} i K_{3,3} nie s _{}a planarne.