1. Twierdzenie o drodze zamkniętej w grafie.

Drogę w grafie , w której początek pokrywa się z końcem nazywa się drogą zamkniętą.

2. Definicja cyklu w grafie.

Drogę zamkniętą, w której wszystkie krawędzie i wierzchołki są różne nazywamy cyklem.

3. Definicja wierzchołków sąsiednich w grafie.

Wierzchołek V nazywamy sąsiednim do U w grafie G, jeżeli istnieje krawędź o początku U i końcu V.

4. Definicja grafu nieskierowanego i acyklicznego.

Graf nie zawierający cykli nazywamy grafem acyklicznym.

Graf , w którym krawędź ma 2 końce , nazywamy nieskierowanym.

5. Pętla w grafie i krawędzie wielokrotne.

Krawędź o tym samym początku i końcu nazywamy pętlą.

Dwie krawędzie o tym samym początku i końcu nazywamy krawędziami wielokrotnymi.

6. Relacja osiągalności i spójności w grafie.

Wierzchołek V nazywamy osiągalnym z wierzchołka U, jeżeli istnieje droga o początku U i końcu V.

Graf, w którym każdy wierzchołek jest osiągalny z każdego innego nazywamy Graffem spójnym.

7. Twierdzenie, kiedy droga jest cyklem.

Każda droga zamknięta o długości >= 3 o różnych wierzchołkach jest cyklem.

8. Definicja izomorfizmu grafu.

Grafy G i H nazywamy izomorficznymi, jeżeli istnieje bijekcja zbioru wierzchołków grafu G na zbiór wierzchołków grafu H , która zachowuje strukturę grafu (krawędzie). Oznacza to, że grafy G i H są tym samym grafem, jedynie poddanym jakiejś permutacji wierzchołków.

Ǝ α: V(G) → V(H), α: E(G) → E(H), taka że: ∀ V,W ∊ V(g), (V,W) ∊ E(G) ↔ (α(V), α(W)) ∊ E(H).

9. Własności grafów izomorficznych.

Izomorfizm grafów zachowuje właściwie wszystkie interesujące własności, na przykład: liczbę wierzchołków, liczbę krawędzi, stopnie wierzchołków, spójność, planarność.

10. Definicja stopnia wierzchołka grafu.

Stopień wierzchołka V = deg(V) = ilość wychodzących z niego pojedynczych krawędzi + 2 * ilość wychodzących z niego pętli.

---