---
title: "Teoria grafów"
lecture_number: 5
has_solutions: true
has_exercises: true
file_format: mystnb
kernelspec:
  name: sagemath
  display_name: SageMath
---

```{include} ../_includes/sagecell-loader.md
```

# Teoria grafów

## Podstawowe pojęcia

:::{narration}

Teoria grafów zajmuje się badaniem struktur złożonych z obiektów (**wierzchołków**) oraz relacji
(**krawędzi**) łączących pary tych obiektów. Modelami grafowymi opisujemy między innymi:

- relacje znajomości w grupie osób
- plany labiryntów
- sieci dróg
- schematy obwodów elektrycznych
- stan rozgrywek w turniejach sportowych
- reprezentacje hierarchii danych.

:::

:::{prf:definition}

**Grafem nieskierowanym** (niezorientowanym) {index}`graf`  nazywamy parę

$$
G = (V, E),
$$

gdzie $V = V(G) = \Set{v_1, \ldots, v_n}$ jest niepustym, skończonym zbiorem
**wierzchołków** {index}`graf; wierzchołek`, natomiast $E = E(G)$ jest skończoną
rodziną nieuporządkowanych par (dwuelementowych podzbiorów) wierzchołków,
zwanych **krawędziami** {index}`graf; krawędź`.

:::

:::{prf:remark}

1. Krawędź łączącą wierzchołki $u,v \in V$ zapisujemy krótko jako $uv .$

2. W sensie powyższej definicji nie dopuszczamy krawędzi postaci $vv$
   (łączącej wierzchołek sam ze sobą) nazywanej {index}`graf; pętla` **pętlą**).

3. Nie dopuszczamy również kilku krawędzi łączących dwa wierzchołki
   (tak zwane {index}`graf; krawędź wielokrotna` **krawędzie wielokrotne**).

4. Ponieważ w wielu zastosowaniach zarówno pętle jak i krawędzie wielokrotne są przydatne,
   to rozważa się modyfikacje powyższej definicji (na przykład **multigrafy** {index}`multigraf` dopuszczają krawędzie wielokrotne).

5. W niektórych źródłach powyższa definicja (bez pętli i bez krawędzi wielokrotnych) odnosi się do
   {index}`graf; prosty` **nieskierowanych grafów prostych**, zaś samo pojęcie grafu dopuszcza te dwie możliwości.

:::

:::{prf:definition}

Wierzchołki $u,v \in V$ połączone krawędzią $uv \in E$ nazywamy {index}`graf; wierzchołki sąsiednie` **sąsiednimi**, a krawędź $uv$ -- **incydentną** {index}`graf; incydencja`
z wierzchołkami $u$ i $v .$

**Stopniem** {index}`graf; stopień wierzchołka` wierzchołka $v$, oznaczanym $\deg(v)$,
nazywamy liczbę krawędzi incydentnych z $v$ (jeśli dopuszczamy pętle, to każdą liczymy dwukrotnie).

:::

:::{prf:remark}

1. Wierzchołek stopnia $0$ nazywamy **izolowanym** {index}`graf; wierzchołek izolowany`.
2. Wierzchołek stopnia $1$ nazywamy **liściem** {index}`graf; liść`.
3. W grafie prostym stopień wierzchołka jest równy liczbie jego sąsiadów.

:::

:::{prf:lemma} O uściskach dłoni

Dla dowolnego grafu $G=(V,E)$ zachodzi

$$
\sum_{v \in V} \deg(v) = 2|E|.
$$

W szczególności liczba wierzchołków o nieparzystym stopniu jest parzysta.

:::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:example}

Dla grafu $G$ o wierzchołkach $V=\Set{a,b,c,d}$ i krawędziach $E=\Set{ab,bc,cd,da,ac}$ mamy

```{math}
\deg(a) = 3, \quad \deg(b) = 2, \quad \deg(c) = 3, \quad \deg(d) = 2.
```

Suma stopni wynosi $10 = 2\cdot 5$, co zgadza się z liczbą krawędzi $|E|=5 .$

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-0.5,-0.5) rectangle (1.5,1.5);

  \node[elem] (a) at (0,1) {a};
  \node[elem] (b) at (1,1) {b};
  \node[elem] (c) at (1,0) {c};
  \node[elem] (d) at (0,0) {d};

  \draw (a) -- (b);
  \draw (b) -- (c);
  \draw (c) -- (d);
  \draw (d) -- (a);
  \draw (a) -- (c);

\end{tikzpicture}
```

::::

:::::

## Drogi, cykle i spójność

:::{prf:definition}

**Drogą** {index}`graf; droga` w grafie $G$ nazywamy naprzemienny ciąg wierzchołków i krawędzi

$$
v_0,\ e_1,\ v_1,\ e_2,\ \ldots,\ e_k,\ v_k,
$$

taki, że każda krawędź $e_i$ łączy wierzchołki $v_{i-1}$ i $v_i$, oraz żadna krawędź się
nie powtarza. Liczbę $k$ nazywamy {index}`graf; długość drogi` **długością drogi**.

Drogę, w której dodatkowo wszystkie wierzchołki są różne, nazywamy {index}`graf; droga prosta` **drogą prostą**.

Jeśli $v_0=v_k$, drogę nazywamy zamkniętą lub {index}`graf; cykl`  **cyklem**.

Jeśli dodatkowo wierzchołki $v_0,\ldots,v_{k-1}$ są parami różne, mówimy o {index}`graf; cykl prosty` **cyklu prostym**.

Graf niezawierający żadnego cyklu nazywamy {index}`graf; acykliczny` **acyklicznym**.

:::

:::{prf:definition}

Graf $G$ nazywamy {index}`graf; spójny` **spójnym**, jeśli dla dowolnych dwóch
wierzchołków $u,v \in V(G)$ istnieje droga łącząca $u$ i $v .$

**Podgrafem** {index}`graf; podgraf` grafu $G=(V,E)$ nazywamy każdy graf
$H=(V_H,E_H)$ taki, że $V_H \subseteq V$ oraz $E_H \subseteq E .$

Jeżeli graf $G$ nie jest spójny, to każdy jego maksymalny spójny podgraf nazywamy
**składową** {index}`graf; składowa` grafu $G .$

:::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:example}

Rozważmy graf $G=(V,E)$ z wierzchołkami $V=\Set{a,b,c,d,e,f,g}$
i krawędziami $E=\Set{ab,bc,cd,da,ac,df,fg}$.

1. Ciąg $(g,f,d,a,b,c,a)$ jest **drogą** (używa sześciu różnych krawędzi:
   $gf,fd,da,ab,bc,ca$), ale **nie jest prosta** -- wierzchołek $a$
   powtarza się.

   Natomiast ciąg $(a,b,c,a)$ to **cykl prosty** długości $3 .$
   Sama odnoga, czyli ciąg $(d,f,g)$, jest drogą prostą i -- w oderwaniu od
   reszty grafu -- **acykliczna**.

2. Ponieważ wierzchołek $e$ nie ma żadnych krawędzi, cały graf $G$ **nie
   jest spójny** -- ma dwie **składowe**: $\Set{a,b,c,d,f,g}$ oraz
   $\Set{e}$.

   Trójkąt $H=(\Set{a,b,c},\Set{ab,bc,ac})$ jest **podgrafem**
   pierwszej składowej.

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-0.6,-0.6) rectangle (1.6,3.6);

  \node[elem] (a) at (0,3) {a};
  \node[elem] (b) at (1,3) {b};
  \node[elem] (c) at (1,2) {c};
  \node[elem] (d) at (0,2) {d};
  \node[elem] (f) at (0,1) {f};
  \node[elem] (g) at (0,0) {g};
  \node[elem] (e) at (1,0) {e};

  \draw (a) -- (b);
  \draw (b) -- (c);
  \draw (c) -- (d);
  \draw (d) -- (a);
  \draw (a) -- (c);
  \draw (d) -- (f);
  \draw (f) -- (g);

\end{tikzpicture}
```

::::

:::::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:example}

Rozważmy graf $G=(V,E)$ złożony z 9 wierzchołków oraz dwóch podzbiorów
krawędzi $E_1=\Set{ab,ac,bd,be,cf,cg}$ oraz $E_2=\Set{hi,ij,jh}$.

1. Ciąg $(d,b,a,c,g)$ jest **drogą prostą** długości $4$ w części drzewiastej
   grafu; ponieważ cała ta część nie zawiera żadnego cyklu, jest
   **acykliczna**.

   Kontrastowo, ciąg $(h,i,j,h)$ jest **cyklem prostym**
   długości $3$ w drugiej części grafu.

2. Graf $G$ **nie jest spójny** -- ma dwie **składowe**: drzewo
   $\Set{a,b,c,d,e,f,g}$ oraz trójkąt $\Set{h,i,j}$.

   Biorąc
   $H=(\Set{a,b,c},\Set{ab})$ (a więc pomijając krawędź $ac$), widzimy,
   że **podgraf nie musi zawierać wszystkich krawędzi** łączących swoje
   wierzchołki.

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.2,-0.8) rectangle (2.2,4.6);

  \node[elem] (a) at (0.5,4) {a};
  \node[elem] (b) at (-0.3,3) {b};
  \node[elem] (c) at (1.3,3) {c};
  \node[elem] (d) at (-0.7,2) {d};
  \node[elem] (e) at (0.1,2) {e};
  \node[elem] (f) at (0.9,2) {f};
  \node[elem] (g) at (1.7,2) {g};

  \node[elem] (h) at (0.5,0.9) {h};
  \node[elem] (i) at (0,-0.1) {i};
  \node[elem] (j) at (1,-0.1) {j};

  \draw (a) -- (b);
  \draw (a) -- (c);
  \draw (b) -- (d);
  \draw (b) -- (e);
  \draw (c) -- (f);
  \draw (c) -- (g);

  \draw (h) -- (i);
  \draw (i) -- (j);
  \draw (j) -- (h);

\end{tikzpicture}
```

::::

:::::

## Podstawowe klasy grafów

:::{narration}

Wśród wszystkich grafów wyróżnia się kilka klas o szczególnie regularnej
strukturze, które posłużą nam jako podstawowe przykłady i "cegiełki" w dalszej
części wykładu.

:::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:definition}
:label: def-graf-pusty

**Grafem pustym** (bezkrawędziowym) {index}`graf; pusty` nazywamy graf
$N_n=(V,E)$ o $|V|=n$ wierzchołkach, w którym $E=\emptyset .$ Każdy
wierzchołek grafu pustego jest izolowany, tzn. $\deg(v)=0$ dla każdego
$v\in V .$

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-0.5,0.5) rectangle (0.5,3.5);

  \node[elem] (a) at (0,3) {a};
  \node[elem] (b) at (0,2) {b};
  \node[elem] (c) at (0,1) {c};

\end{tikzpicture}
```

::::

:::::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:definition}
:label: def-graf-pelny

**Grafem pełnym** {index}`graf; pełny` nazywamy graf $K_n=(V,E)$ o $n$
wierzchołkach, w którym każde dwa różne wierzchołki są sąsiednie, czyli

```{math}
E=\Set{uv : u,v\in V,\ u\neq v}.
```

Liczba krawędzi grafu pełnego wynosi $|E|=\binom n 2 .$

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-0.5,-0.5) rectangle (1.5,1.5);

  \node[elem] (a) at (0,1) {1};
  \node[elem] (b) at (1,1) {2};
  \node[elem] (c) at (1,0) {3};
  \node[elem] (d) at (0,0) {4};

  \draw (a) -- (b);
  \draw (b) -- (c);
  \draw (c) -- (d);
  \draw (d) -- (a);
  \draw (a) -- (c);
  \draw (b) -- (d);

\end{tikzpicture}
```

::::

:::::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:definition}
:label: def-graf-regularny

Dla ustalonego $k\in\nn_0$,
graf $G=(V,E)$ nazywamy **$k$-regularnym**, {index}`graf; regularny`
jeśli $\deg(v)=k$ dla każdego $v\in V .$

Graf nazywamy **regularnym**, jeśli jest $k$-regularny dla pewnego $k .$

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.4,0.0) rectangle (1.4,3.8);

  \node[elem] (a) at (0,2.4) {a};
  \node[elem] (b) at (-0.8,3.2) {b};
  \node[elem] (c) at (0.8,3.2) {c};

  \node[elem] (d) at (0,1.4) {d};
  \node[elem] (e) at (-0.8,0.6) {e};
  \node[elem] (f) at (0.8,0.6) {f};

  \draw (a) -- (b);
  \draw (b) -- (c);
  \draw (c) -- (a);

  \draw (d) -- (e);
  \draw (e) -- (f);
  \draw (f) -- (d);

  \draw (a) -- (d);
  \draw (b) -- (e);
  \draw (c) -- (f);

\end{tikzpicture}
```

::::

:::::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:definition}
:label: def-cykl-cn

Dla $n\geq 3$, **cyklem** $C_n$ {index}`graf; cykl $C_n$` nazywamy spójny i $2$-regularny graf o
$n$ wierzchołkach.

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elem] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.95, 0.31) {2};
  \node[elem] (v3) at (0.59, -0.81) {3};
  \node[elem] (v4) at (-0.59, -0.81) {4};
  \node[elem] (v5) at (-0.95, 0.31) {5};

  \draw (v1) -- (v2);
  \draw (v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v5) -- (v1);

\end{tikzpicture}
```

::::

:::::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:definition}
:label: def-graf-liniowy

Dla $n\geq 2$, **grafem liniowym** (**ścieżką**) $P_n$ {index}`graf; liniowy`
{index}`ścieżka` nazywamy graf powstały przez usunięcie dowolnej krawędzi z cyklu $C_n .$

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elem] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.95, 0.31) {2};
  \node[elem] (v3) at (0.59, -0.81) {3};
  \node[elem] (v4) at (-0.59, -0.81) {4};
  \node[elem] (v5) at (-0.95, 0.31) {5};

  \draw (v1) -- (v2);
  \draw (v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);

\end{tikzpicture}
```

::::

:::::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:definition}
:label: def-drzewo

Graf $G$ nazywamy **drzewem** {index}`drzewo`, jeśli jest spójny i
acykliczny.

Wierzchołki stopnia $1$ w drzewie nazywamy **liśćmi**
{index}`drzewo; liść`, a pozostałe -- **wierzchołkami wewnętrznymi**
{index}`drzewo; wierzchołek wewnętrzny`.

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elem] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.95, 0.31) {2};
  \node[elem] (v3) at (0.59, -0.81) {3};
  \node[elem] (v4) at (-0.59, -0.81) {4};
  \node[elem] (v5) at (-0.95, 0.31) {5};

  \draw (v1) -- (v2);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v1) -- (v4);

\end{tikzpicture}
```

::::

:::::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:definition}
:label: def-las

Graf $G$ nazywamy **lasem** {index}`las`, jeśli jest acykliczny
(niekoniecznie spójny).

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elem] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.95, 0.31) {2};
  \node[elem] (v3) at (0.59, -0.81) {3};
  \node[elem] (v4) at (-0.59, -0.81) {4};
  \node[elem] (v5) at (-0.95, 0.31) {5};

  \draw (v1) -- (v4);
  \draw (v5) -- (v1);

  \draw (v3) -- (v2);

\end{tikzpicture}
```

::::

:::::

:::{prf:remark}

1. Grafy puste i pełne to skrajne przypadki grafów regularnych --
   odpowiednio $0$-regularne i $(n-1)$-regularne na $n$ wierzchołkach.

2. W odróżnieniu od cyklu, graf $P_n$ nie jest regularny
   (dwa końcowe wierzchołki mają stopień $1$, pozostałe -- stopień $2$).

3. Drzewo o $n$ wierzchołkach ma dokładnie $n-1$ krawędzi.

   Jest to zresztą równoważna charakteryzacja drzewa (graf jest spójny o $n-1$
   krawędziach wtedy i tylko wtedy, gdy jest drzewem).

4. Las to rozłączna suma drzew -- jego składowe (w sensie wcześniejszej
   definicji) są drzewami.

   W szczególności graf pusty $N_n$ jest lasem
   złożonym z $n$ jedno-wierzchołkowych drzew.

5. Ścieżka $P_n$ i każde drzewo są grafami acyklicznymi, ale nie każdy graf
   acykliczny jest spójny -- stąd potrzebne jest osobne pojęcie lasu.

:::

## Grafy dwudzielne

:::{prf:definition}

Graf $G=(V,E)$ nazywamy {index}`graf; dwudzielny` **dwudzielnym**, jeśli zbiór $V$
można podzielić na dwa rozłączne podzbiory $V_1, V_2$ (**klasy podziału**) tak, że żadne
dwa wierzchołki należące do tej samej klasy nie są sąsiednie.

Piszemy wtedy $G(V_1,V_2) .$

:::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:example}

1. Cykl $C_6$ jest dwudzielny
   -- wierzchołki można podzielić na dwie klasy
   $V_1 = \Set{1,3,5}$ i $V_2 = \Set{2,4,6}$
   , odwiedzane na przemian.

2. Niech $Q_3=(V,E)$ będzie {index}`graf; sześcianu` **grafem sześcianu**:
   wierzchołkami są wszystkie ciągi binarne długości $3$ (czyli $V=\Set{0,1}^3$,
   $|V|=8$), a krawędź łączy dwa ciągi wtedy i tylko wtedy, gdy różnią się
   dokładnie na jednej pozycji.

   $Q_3$ jest grafem dwudzielnym $G(V_1,V_2)$, gdzie

   - $V_1 = \Set{\text{ciągi o parzystej liczbie jedynek}}$
   - $V_2 = \Set{\text{ciągi o nieparzystej liczbie jedynek}} .$

   Istotnie, zmiana jednej współrzędnej zawsze zmienia parzystość liczby
   jedynek o dokładnie jeden, więc żadna krawędź nie łączy dwóch wierzchołków
   z tej samej klasy.

   Patrząc wyłącznie na strukturę grafu (bez etykiet i kolorów)
   dwudzielność $Q_3$ wcale nie rzuca się w oczy
   -- ujawnia się dopiero po pokolorowaniu
   wierzchołków zgodnie z parzystością.

   $Q_3$ jest grafem $3$-regularnym --
   widać więc, że regularność i dwudzielność to własności od siebie
   niezależne.

:::

:::{prf:definition}

Graf dwudzielny $G(V_1,V_2)$, w którym **każdy** wierzchołek z $V_1$ jest połączony
z **każdym** wierzchołkiem z $V_2$, nazywamy **pełnym grafem dwudzielnym**
{index}`graf; dwudzielny; pełny` i oznaczamy przez $K_{r,s}$, gdzie $r=|V_1|$, $s=|V_2| .$

Graf $K_{1,s}$ nazywamy **gwiazdą** {index}`graf; gwiazda`.

:::

:::{prf:remark}

W grafie $K_{r,s}$ liczba wierzchołków wynosi $r+s$, a liczba krawędzi $r\cdot s .$

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw=blue, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemOdd/.style={draw=red, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.4,-1.5) rectangle (1.4,1.5);

  \node[elemOdd] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.87, 0.5) {2};
  \node[elemOdd] (v3) at (0.87, -0.5) {3};
  \node[elem] (v4) at (0, -1) {4};
  \node[elemOdd] (v5) at (-0.87, -0.5) {5};
  \node[elem] (v6) at (-0.87, 0.5) {6};

  \draw (v1) -- (v2);
  \draw (v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v5) -- (v6);
  \draw (v6) -- (v1);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elemA/.style={draw, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\normalsize},
    elemB/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\normalsize}]

  \path (-0.6,-0.6) rectangle (3.4,3.4);

  \node[elemA] (000) at (0,0)     {$000$};
  \node[elemB] (100) at (2,0)     {$100$};
  \node[elemA] (110) at (2,2)     {$110$};
  \node[elemB] (010) at (0,2)     {$010$};

  \node[elemB] (001) at (0.7,0.7) {$001$};
  \node[elemA] (101) at (2.7,0.7) {$101$};
  \node[elemB] (111) at (2.7,2.7) {$111$};
  \node[elemA] (011) at (0.7,2.7) {$011$};

  \draw (000) -- (100);
  \draw (100) -- (110);
  \draw (110) -- (010);
  \draw (010) -- (000);

  \draw (001) -- (101);
  \draw (101) -- (111);
  \draw (111) -- (011);
  \draw (011) -- (001);

  \draw (000) -- (001);
  \draw (100) -- (101);
  \draw (110) -- (111);
  \draw (010) -- (011);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw=blue, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemOdd/.style={draw=red, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.2,-2) rectangle (1.2,2);

  \node[elem] (u1) at (-0.7, 1.5) {1};
  \node[elem] (u2) at (-0.7, 0.5) {3};
  \node[elem] (u3) at (-0.7, -0.5) {5};
  \node[elem] (u4) at (-0.7, -1.5) {7};
  \node[elemOdd] (v1) at (0.7, 1) {2};
  \node[elemOdd] (v2) at (0.7, 0) {4};
  \node[elemOdd] (v3) at (0.7, -1) {6};

  \draw (u1) -- (v1);
  \draw (u1) -- (v2);
  \draw (u1) -- (v3);
  \draw (u2) -- (v1);
  \draw (u2) -- (v2);
  \draw (u2) -- (v3);
  \draw (u3) -- (v1);
  \draw (u3) -- (v2);
  \draw (u3) -- (v3);
  \draw (u4) -- (v1);
  \draw (u4) -- (v2);
  \draw (u4) -- (v3);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw=blue, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemOdd/.style={draw=red, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elem] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.95, 0.31) {2};
  \node[elem] (v3) at (0.59, -0.81) {3};
  \node[elem] (v4) at (-0.59, -0.81) {4};
  \node[elem] (v5) at (-0.95, 0.31) {5};
  \node[elemOdd] (v6) at (0, 0) {6};

  \draw (v6) -- (v1);
  \draw (v6) -- (v2);
  \draw (v6) -- (v3);
  \draw (v6) -- (v4);
  \draw (v6) -- (v5);

\end{tikzpicture}
```

::::

:::::

:::{prf:theorem}

Graf $G$ jest dwudzielny wtedy i tylko wtedy, gdy każdy jego cykl ma parzystą długość.

W szczególności każdy graf acykliczny jest dwudzielny.

:::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:example}

1. Cykl $C_5$ ma długość $5$ (nieparzystą), więc $C_5$ **nie jest** dwudzielny.

2. Rozważmy graf $G$ powstały z cyklu $C_6$ z dodaną jedną krawędzią.

   Sam cykl $C_6$ jest dwudzielny, jednak dodana przekątna łączy dwa
   wierzchołki "tego samego koloru" -- $G$ przestaje być dwudzielny.

   Najłatwiej to udowodnić wskazując nieparzysty cykl.

   Ten przykład pokazuje, że obecność dużego, parzystego cyklu jako "szkieletu"
   grafu **nie wystarcza**, by wnioskować o jego dwudzielności.

   Trzeba sprawdzić **wszystkie** cykle w grafie, a nie tylko ten najbardziej
   oczywisty.

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elem] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.87, 0.5) {2};
  \node[elem] (v3) at (0.87, -0.5) {3};
  \node[elem] (v4) at (0, -1) {4};
  \node[elem] (v5) at (-0.87, -0.5) {5};
  \node[elem] (v6) at (-0.87, 0.5) {6};

  \draw[red, thick] (v1) -- (v2);
  \draw [red, thick](v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v5) -- (v6);
  \draw (v6) -- (v1);

  \draw[red, thick] (v1) -- (v3);

\end{tikzpicture}
```

::::

:::::

## Problem mostów królewieckich

:::{narration}

W 1736 roku Leonhard Euler rozwiązał następujący problem. Przez miasto Królewiec
(dzisiejszy Kaliningrad) przepływa rzeka Pregoła, dzieląc miasto na cztery części,
połączone siedmioma mostami. Mieszkańcy zastanawiali się, czy można odbyć spacer po
mieście, przechodząc przez każdy most **dokładnie raz** i wracając do punktu wyjścia.

:::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:remark}

Sytuację tę można przedstawić jako multigraf $G=(V,E)$, w którym wierzchołki
$V=\Set{A,B,C,D}$ odpowiadają czterem częściom miasta, a siedem krawędzi -- siedmiu
mostom (niektóre pary części miasta są połączone więcej niż jednym mostem).

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\large}]

  \path (-1.7,-1.4) rectangle (1.7,1.4);

  \node[elem] (A) at (-1, 0) {A};
  \node[elem] (B) at (0, 0.9) {B};
  \node[elem] (C) at (0, -0.9) {C};
  \node[elem] (D) at (1, 0) {D};

  \draw (A) to[bend left=18] (B);
  \draw (A) to[bend right=18] (B);
  \draw (A) to[bend left=18] (C);
  \draw (A) to[bend right=18] (C);
  \draw (A) -- (D);
  \draw (B) -- (D);
  \draw (C) -- (D);

\end{tikzpicture}
```

::::

:::::

:::{prf:definition}

**Drogą Eulera** {index}`graf; Eulera; droga` w grafie $G$ nazywamy drogę zawierającą
każdą krawędź grafu $G$ dokładnie raz (wierzchołki mogą się powtarzać).

Zamkniętą drogę Eulera nazywamy {index}`graf; Eulera; cykl` **cyklem Eulera**.

Graf, w którym istnieje cykl Eulera, nazywamy {index}`graf; Eulera` **grafem eulerowskim**.

:::

:::{prf:theorem} Kryterium Eulera

W (multi)grafie można znaleźć cykl Eulera wtedy i tylko wtedy, gdy graf jest spójny i
każdy jego wierzchołek ma parzysty stopień.

:::

:::{prf:example}

W grafie mostów królewieckich mamy $\deg(A)=5$, $\deg(B)=\deg(C)=\deg(D)=3$ -- wszystkie
cztery wierzchołki mają stopień nieparzysty. Na mocy powyższego twierdzenia **nie
istnieje** więc ani cykl, ani nawet droga Eulera: nie da się przejść przez wszystkie
mosty, korzystając z każdego dokładnie raz.

:::

::::::{container} side-by-side

:::::{container} column-three-fourth

::::{prf:remark}

1. Spójne grafy $n$-regularne są eulerowskie wtedy i tylko wtedy, gdy $n$ jest parzyste.

   Stąd na przykład $K_{5}$ i $C_6$ są eulerowskie (są odpowiednio $2$- i $4$-regularne),
   zaś $K_6$ nie jest eulerowski.

2. Kryterium Eulera ma poglądowe zastosowanie do popularnej zagadki:

   :::{container} center-text

   ***Narysuj dany rysunek jednym pociągnięciem, nie odrywając ołówka od kartki i nie kreśląc żadnej linii dwukrotnie.***

   :::

   Pytanie to jest dokładnie pytaniem o istnienie drogi (lub cyklu) Eulera w grafie odpowiadającym temu rysunkowi.

   Rysunek da się nakreślić jednym pociągnięciem wtedy i tylko wtedy, gdy ma on zero lub dwa wierzchołki nieparzystego stopnia (jeśli dwa, to trzeba zacząć w jednym z nich i skończyć w drugim).

3. Gdy graf **nie jest** eulerowski (ma więcej niż dwa wierzchołki nieparzystego stopnia), naturalne staje się pytanie:

   :::{container} center-text

   ***O ile najmniej trzeba "wydłużyć" trasę (dopuszczając ponowne przejście po już odwiedzonych krawędziach), aby przejść każdą krawędź co najmniej raz i wrócić do punktu startu?***

   :::

   To tak zwany **problem chińskiego listonosza** {index}`problem chińskiego listonosza`
   -- odpowiada on np. listonoszowi, który musi dostarczyć przesyłki na każdą ulicę swojego rejonu i wrócić na pocztę,
   pokonując możliwie najkrótszą trasę.

   Rozwiązanie polega na sparowaniu wszystkich wierzchołków nieparzystego stopnia
   (jest ich parzyście wiele, na mocy lematu o uściskach dłoni)
   i podwojeniu krawędzi na najkrótszych drogach łączących każdą parę.

   W odróżnieniu od pokrewnego, ale znacznie trudniejszego problemu komiwojażera
   (związanego z cyklem Hamiltona),
   problem chińskiego listonosza daje się rozwiązać efektywnie, w czasie wielomianowym.

::::

:::::

:::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elem] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.95, 0.31) {2};
  \node[elem] (v3) at (0.59, -0.81) {3};
  \node[elem] (v4) at (-0.59, -0.81) {4};
  \node[elem] (v5) at (-0.95, 0.31) {5};

  \draw (v1) -- (v2);
  \draw (v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v5) -- (v1);
  \draw (v1) -- (v3);
  \draw (v1) -- (v4);
  \draw (v2) -- (v4);
  \draw (v2) -- (v5);
  \draw (v3) -- (v5);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.4,-1.5) rectangle (1.4,1.5);

  \node[elem] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.87, 0.5) {2};
  \node[elem] (v3) at (0.87, -0.5) {3};
  \node[elem] (v4) at (0, -1) {4};
  \node[elem] (v5) at (-0.87, -0.5) {5};
  \node[elem] (v6) at (-0.87, 0.5) {6};

  \draw (v1) -- (v2);
  \draw (v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v5) -- (v6);
  \draw (v6) -- (v1);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.4,-1.5) rectangle (1.4,1.5);

  \node[elem] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.87, 0.5) {2};
  \node[elem] (v3) at (0.87, -0.5) {3};
  \node[elem] (v4) at (0, -1) {4};
  \node[elem] (v5) at (-0.87, -0.5) {5};
  \node[elem] (v6) at (-0.87, 0.5) {6};

  \draw (v1) -- (v2);
  \draw (v1) -- (v3);
  \draw (v1) -- (v4);
  \draw (v1) -- (v5);
  \draw (v1) -- (v6);

  \draw (v2) -- (v3);
  \draw (v2) -- (v4);
  \draw (v2) -- (v5);
  \draw (v2) -- (v6);

  \draw (v3) -- (v4);
  \draw (v3) -- (v5);
  \draw (v3) -- (v6);

  \draw (v4) -- (v5);
  \draw (v4) -- (v6);

  \draw (v5) -- (v6);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemOdd/.style={draw=red, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-0.6,-0.6) rectangle (2.6,2.6);

  \node[elem]    (a1) at (0,2) {1};
  \node[elemOdd] (a2) at (1,2) {2};
  \node[elem]    (a3) at (2,2) {3};

  \node[elemOdd] (b1) at (0,1) {4};
  \node[elem]    (b2) at (1,1) {5};
  \node[elemOdd] (b3) at (2,1) {6};

  \node[elem]    (c1) at (0,0) {7};
  \node[elemOdd] (c2) at (1,0) {8};
  \node[elem]    (c3) at (2,0) {9};

  \draw (a1) -- (a2);
  \draw (a2) -- (a3);
  \draw (b1) -- (b2);
  \draw (b2) -- (b3);
  \draw (c1) -- (c2);
  \draw (c2) -- (c3);

  \draw (a1) -- (b1);
  \draw (b1) -- (c1);
  \draw (a2) -- (b2);
  \draw (b2) -- (c2);
  \draw (a3) -- (b3);
  \draw (b3) -- (c3);

  \draw[red, thick] (a1) to[bend left=15]  (a2);
  \draw[red, thick] (a1) to[bend right=15] (b1);
  \draw[red, thick] (b3) to[bend left=15]  (c3);
  \draw[red, thick] (c3) to[bend right=15] (c2);

\end{tikzpicture}
```

:::::

::::::

## Grafy Hamiltona

:::{prf:definition}

**Cyklem Hamiltona** {index}`graf; Hamiltona; cykl` nazywamy cykl prosty zawierający
**wszystkie** wierzchołki grafu $G .$

Graf, w którym istnieje cykl Hamiltona, nazywamy
{index}`graf; Hamiltona`
**grafem hamiltonowskim**.

:::

:::{prf:remark}

W odróżnieniu od grafów Eulera (gdzie kluczowa jest liczba krawędzi), warunek
hamiltonowskości dotyczy wszystkich wierzchołków.

Nie znamy prostej charakteryzacji
analogicznej do twierdzenia Eulera -- sprawdzenie hamiltonowskości grafu jest w
ogólności trudne obliczeniowo.

:::

:::{prf:theorem} Diraca

Niech $G$ będzie grafem prostym o $n\geq 3$ wierzchołkach.
Jeżeli

$$
\forall v\in V(G) \quad \deg(v) \geq \frac n 2,
$$

to $G$ jest hamiltonowski.

:::

:::{prf:example}

Graf pełny $K_n$ dla $n\geq 3$ jest hamiltonowski -- spełnia (z nadmiarem) założenie
twierdzenia Diraca, gdyż $\deg(v) = n-1 \geq \frac n 2 .$

:::

::::{container} side-by-side

:::{container} column-two-third

:::{prf:example} Droga Hamiltona w grafie ruchów skoczka

Skoczek szachowy porusza się o wektor $(\pm 1, \pm 2)$ lub $(\pm 2, \pm 1)$.
Na planszy $4\times 5$ (20 pól) istnieje **otwarta trasa skoczka**
{index}`skoczek szachowy; trasa` -- czyli droga Hamiltona
w grafie, którego wierzchołkami są pola planszy,
a krawędziami legalne ruchy skoczka.

Skoczek zawsze przemieszcza się
z pola jednego koloru na pole koloru przeciwnego
-- to
dwukolorowanie pokazuje, że graf ruchów skoczka jest
**dwudzielny**.

:::

:::

:::{container} column-one-third

```{tikz}
\begin{tikzpicture}[scale=1.5, >=stealth,
    elem/.style={draw=blue, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemOdd/.style={draw=red, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-0.7,-0.7) rectangle (4.6,5.9);

  \node[elem]    (n1)  at (0,0)     {1};
  \node[elemOdd] (n2)  at (2.6,1.3) {2};
  \node[elem]    (n3)  at (3.9,3.9) {3};
  \node[elemOdd] (n4)  at (1.3,5.2) {4};
  \node[elem]    (n5)  at (0,2.6)   {5};
  \node[elemOdd] (n6)  at (1.3,0)   {6};
  \node[elem]    (n7)  at (3.9,1.3) {7};
  \node[elemOdd] (n8)  at (2.6,3.9) {8};
  \node[elem]    (n9)  at (0,5.2)   {9};
  \node[elemOdd] (n10) at (1.3,2.6) {10};
  \node[elem]    (n11) at (2.6,0)   {11};
  \node[elemOdd] (n12) at (0,1.3)   {12};
  \node[elem]    (n13) at (1.3,3.9) {13};
  \node[elemOdd] (n14) at (3.9,5.2) {14};
  \node[elem]    (n15) at (2.6,2.6) {15};
  \node[elemOdd] (n16) at (3.9,0)   {16};
  \node[elem]    (n17) at (1.3,1.3) {17};
  \node[elemOdd] (n18) at (3.9,2.6) {18};
  \node[elem]    (n19) at (2.6,5.2) {19};
  \node[elemOdd] (n20) at (0,3.9)   {20};

  % Ścieżka Hamiltona
  \draw[->, thick] (n1)  -- (n2);
  \draw[->, thick] (n2)  -- (n3);
  \draw[->, thick] (n3)  -- (n4);
  \draw[->, thick] (n4)  -- (n5);
  \draw[->, thick] (n5)  -- (n6);
  \draw[->, thick] (n6)  -- (n7);
  \draw[->, thick] (n7)  -- (n8);
  \draw[->, thick] (n8)  -- (n9);
  \draw[->, thick] (n9)  -- (n10);
  \draw[->, thick] (n10) -- (n11);
  \draw[->, thick] (n11) -- (n12);
  \draw[->, thick] (n12) -- (n13);
  \draw[->, thick] (n13) -- (n14);
  \draw[->, thick] (n14) -- (n15);
  \draw[->, thick] (n15) -- (n16);
  \draw[->, thick] (n16) -- (n17);
  \draw[->, thick] (n17) -- (n18);
  \draw[->, thick] (n18) -- (n19);
  \draw[->, thick] (n19) -- (n20);

  % Pozostałe krawędzie skoczka
  \draw[gray, thick] (n1)  -- (n10);
  \draw[gray, thick] (n2)  -- (n5);
  \draw[gray, thick] (n2)  -- (n13);
  \draw[gray, thick] (n3)  -- (n10);
  \draw[gray, thick] (n4)  -- (n15);
  \draw[gray, thick] (n5)  -- (n8);
  \draw[gray, thick] (n6)  -- (n15);
  \draw[gray, thick] (n7)  -- (n10);
  \draw[gray, thick] (n8)  -- (n17);
  \draw[gray, thick] (n10) -- (n19);
  \draw[gray, thick] (n11) -- (n18);
  \draw[gray, thick] (n12) -- (n15);
  \draw[gray, thick] (n13) -- (n18);
  \draw[gray, thick] (n15) -- (n20);
  \draw[gray, thick] (n17) -- (n20);

\end{tikzpicture}
```

:::

::::

::::::{container} side-by-side

:::::{container} column-three-fourth

::::{exercise}
:class: [exercise]

Czy graf pełny dwudzielny $K_{2,3}$ jest hamiltonowski.

::::

:::{solution-without-reference}
:class: [solution] dropdown

Cykl Hamiltona w grafie dwudzielnym $G(V_1,V_2)$ musi na przemian odwiedzać wierzchołki
z $V_1$ i z $V_2$, co wymaga $|V_1|=|V_2| .$

Dla $K_{2,3}$ mamy $|V_1|=2 \neq 3=|V_2|$, więc graf ten **nie jest** hamiltonowski.

:::

:::::

:::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw=blue, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemOdd/.style={draw=red, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.2,-1.5) rectangle (1.2,1.5);

  \node[elem] (u1) at (-0.7, 0.6) {2};
  \node[elem] (u2) at (-0.7, -0.6) {4};
  \node[elemOdd] (v1) at (0.7, 1) {1};
  \node[elemOdd] (v2) at (0.7, 0) {3};
  \node[elemOdd] (v3) at (0.7, -1) {5};

  \draw (u1) -- (v1);
  \draw (u1) -- (v2);
  \draw (u1) -- (v3);
  \draw (u2) -- (v1);
  \draw (u2) -- (v2);
  \draw (u2) -- (v3);

\end{tikzpicture}
```

:::::

::::::

## Grafy planarne i wzór Eulera

:::{narration}

Każdy graf można narysować na płaszczyźnie, przyporządkowując wierzchołkom punkty,
a krawędziom -- łuki krzywych łączące odpowiednie punkty. Interesujące jest jednak, czy
da się to zrobić **bez przecięć** krawędzi.

:::

:::{prf:definition}

Graf nazywamy {index}`graf; planarny` **planarnym**, jeśli można jego reprezentację narysować na
płaszczyźnie tak, aby żadne dwie krawędzie się nie przecinały (poza wspólnymi końcami).

Konkretny taki rysunek nazywamy {index}`graf; płaski` **grafem płaskim**.

:::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:example}

Grafami planarnymi są między innymi: graf pusty, graf pełny $K_4$, wszystkie cykle
$C_n$, wszystkie gwiazdy $K_{1,s}$, a także każdy podgraf grafu planarnego.

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.3,-1.1) rectangle (1.3,1.4);

  \node[elem] (a) at (0,1) {1};
  \node[elem] (b) at (-0.866,-0.5) {2};
  \node[elem] (c) at (0.866,-0.5) {3};
  \node[elem] (d) at (0,0) {4};

  \draw (a) -- (b);
  \draw (b) -- (c);
  \draw (c) -- (a);
  \draw (d) -- (a);
  \draw (d) -- (b);
  \draw (d) -- (c);

\end{tikzpicture}
```

::::

:::::

:::{prf:remark}

1. W sensie przyjętej definicji grafu, pojęcie grafu płaskiego jest sztuczne
   -- graf to przecież para zbiorów nie mających nic wspólnego z płaszczyzną.

2. Graf płaski dzieli płaszczyznę na obszary zwane {index}`graf; płaski ściana` **ścianami**.
   Jedna z nich, nieograniczona, to ściana zewnętrzna.

:::

:::{prf:theorem} Wzór Eulera

Dla dowolnego spójnego grafu płaskiego $G=(V,E)$ o:

- $W=|V|$ wierzchołkach,
- $K=|E|$ krawędziach i
- $S$ ścianach

zachodzi zależność

$$
W - K + S = 2.
$$

:::

:::{prf:corollary}

Z wzoru Eulera wynika, że

- dla każdego prostego grafu planarny o $W\geq 3$ wierzchołkach spełniona jest nierówność

$$
K \leq 3W-6
$$

- jeśli dodatkowo jest dwudzielny, to wówczas

$$
K \leq 2W-4.
$$

:::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:example}

Graf pełny dwudzielny $K_{3,3}$ ma $W=6$ wierzchołków oraz $K=3\cdot 3=9$
krawędzi.

Pierwsza z powyższych nierówności jest spełniona:

$$
9 \leq 3\cdot 6-6 = 12,
$$

więc sama w sobie **nie wystarcza**, by wykluczyć planarność $K_{3,3} .$

Jednak $K_{3,3}$ jest grafem dwudzielnym, więc gdyby był planarny, musiałby
spełniać ostrzejszą nierówność $K\leq 2W-4 .$ Tymczasem

$$
9 \not \leq 2\cdot 6-4 = 8.
$$

Zatem $K_{3,3}$ nie jest planarny.

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw=blue, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemOdd/.style={draw=red, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.2,-1.5) rectangle (1.2,1.5);

  \node[elemOdd] (u1) at (-0.7, 1) {1};
  \node[elemOdd] (u2) at (-0.7, 0) {3};
  \node[elemOdd] (u3) at (-0.7, -1) {5};
  \node[elem] (v1) at (0.7, 1) {2};
  \node[elem] (v2) at (0.7, 0) {4};
  \node[elem] (v3) at (0.7, -1) {6};

  \draw (u1) -- (v1);
  \draw (u1) -- (v2);
  \draw (u1) -- (v3);
  \draw (u2) -- (v1);
  \draw (u2) -- (v2);
  \draw (u2) -- (v3);
  \draw (u3) -- (v1);
  \draw (u3) -- (v2);
  \draw (u3) -- (v3);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw=blue, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemOdd/.style={draw=red, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.4,-1.5) rectangle (1.4,1.5);

  \node[elemOdd] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.87, 0.5) {2};
  \node[elemOdd] (v3) at (0.87, -0.5) {3};
  \node[elem] (v4) at (0, -1) {4};
  \node[elemOdd] (v5) at (-0.87, -0.5) {5};
  \node[elem] (v6) at (-0.87, 0.5) {6};

  \draw (v1) -- (v2);
  \draw (v1) -- (v4);
  \draw (v1) -- (v6);

  \draw (v2) -- (v3);
  \draw (v2) -- (v5);

  \draw (v3) -- (v4);
  \draw (v3) -- (v6);

  \draw (v4) -- (v5);

  \draw (v5) -- (v6);

\end{tikzpicture}
```

::::

:::::

::::::{container} side-by-side

:::::{container} column-three-fourth

::::{exercise}
:class: [exercise]

Korzystając ze wzoru Eulera, pokażmy, że graf $K_5$ nie jest planarny.

::::

:::{solution-without-reference}
:class: [solution] dropdown

Graf $K_5$ ma $W=5$ wierzchołków oraz $K=\binom 5 2 = 10$ krawędzi. Gdyby $K_5$ był
planarny, to z nierówności $K\leq 3W-6$ mielibyśmy

$$
10 \leq 3\cdot 5 - 6 = 9,
$$

co jest fałszem. Zatem $K_5$ nie jest planarny.

:::

:::::

:::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elem] (v1) at (0, 1) {1};
  \node[elem] (v2) at (0.95, 0.31) {2};
  \node[elem] (v3) at (0.59, -0.81) {3};
  \node[elem] (v4) at (-0.59, -0.81) {4};
  \node[elem] (v5) at (-0.95, 0.31) {5};

  \draw (v1) -- (v2);
  \draw (v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v5) -- (v1);
  \draw (v1) -- (v3);
  \draw (v1) -- (v4);
  \draw (v2) -- (v4);
  \draw (v2) -- (v5);
  \draw (v3) -- (v5);

\end{tikzpicture}
```

:::::

::::::

:::{prf:definition}

**Grafami Kuratowskiego** {index}`graf; Kuratowskiego` nazywamy grafy $K_5$ oraz $K_{3,3} .$

:::

:::{prf:theorem} Kuratowski

Graf $G$ jest planarny wtedy i tylko wtedy, gdy nie zawiera
podgrafu będącego podziałem grafu Kuratowskiego.

:::

:::::{container} side-by-side

::::{container} column-two-third

:::{prf:remark}

Każdy graf zawierający $K_5$ lub $K_{3,3}$ jako podgraf jest nieplanarny.

Jednak warunek w twierdzeniu Kuratowskiego musi być nieco słabszy
-- dotyczyć dowolnych podziałów tych grafów,
bo istnieją grafy nieplanarne, które nie zawierają podgrafu Kuratowskiego.

Klasycznym przykładem jest {index}`graf; Petersena` graf Petersena,
którego model widać na rysunku.

Po usunięciu wierzchołka $5$ (wraz z jego trzema krawędziami)
wierzchołki w $V_1 = \Set{0,2,6}$ i $V_2 = \Set{1,3,9}$ odpowiadają dwóm trójkom
wierzchołków rozgałęzienia $K_{3,3}$, a wierzchołki $4,7,8$ są
punktami podziału na krawędziach $0\!-\!4\!-\!3$, $2\!-\!7\!-\!9$ oraz
$6\!-\!8\!-\!1 .$

Ponieważ podział grafu nieplanarnego jest sam w sobie
nieplanarny (podział "wydłuża" krawędzie, ale nie zmienia struktury
przecięć), z twierdzenia Kuratowskiego wynika, że cały graf Petersena --
jako zawierający podział $K_{3,3}$ -- jest nieplanarny.

:::

::::

::::{container} column-one-third

```{tikz}
\begin{tikzpicture}[scale=2.6, >=stealth,
    elem/.style={draw=gray!15, circle, fill=gray!15, inner sep=0pt, minimum size=6mm, font=\Large},
    elemK/.style={draw=blue, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemKO/.style={draw=red, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemR/.style={draw=gray!15, circle, fill=gray!15, inner sep=0pt, minimum size=6mm, font=\Large}]

  \path (-1.6,-1.5) rectangle (1.6,1.7);

  \node[elemK] (o1) at (0, 1.3) {0};
  \node[elemKO] (o2) at (-1.236, 0.402) {1};
  \node[elemK] (o3) at (-0.764, -1.052) {2};
  \node[elemKO] (o4) at (0.764, -1.052) {3};
  \node[elemR] (o5) at (1.236, 0.402) {4};

  \node[elemKO] (i1) at (0, 0.65) {9};
  \node[elemR] (i2) at (-0.618, 0.201) {8};
  \node[elemR] (i3) at (-0.382, -0.526) {7};
  \node[elemK] (i4) at (0.382, -0.526) {6};
  \node[elem]  (i5) at (0.618, 0.201) {5};

  \draw[red, thick] (o1) -- (o2);
  \draw[red, thick] (o2) -- (o3);
  \draw[red, thick] (o3) -- (o4);
  \draw[red, thick] (o4) -- (o5);
  \draw[red, thick] (o5) -- (o1);

  \draw[red, thick] (o1) -- (i1);
  \draw[red, thick] (o2) -- (i2);
  \draw[red, thick] (o3) -- (i3);
  \draw[red, thick] (o4) -- (i4);
  \draw            (o5) -- (i5);

  \draw[red, thick] (i1) -- (i3);
  \draw            (i3) -- (i5);
  \draw            (i5) -- (i2);
  \draw[red, thick] (i2) -- (i4);
  \draw[red, thick] (i4) -- (i1);

\end{tikzpicture}
```

::::

:::::

## Kolorowanie grafów

:::{prf:definition}

Graf $G$ nazywamy {index}`kolorowanie grafu` **$k$-kolorowalnym wierzchołkowo**, jeśli
jego wierzchołki można pokolorować co najwyżej $k$ kolorami tak, aby żadne dwa sąsiednie
wierzchołki nie miały tego samego koloru.

**Liczbą chromatyczną** {index}`liczba chromatyczna` grafu $G$, oznaczaną $\chi(G)$,
nazywamy najmniejszą liczbę $k$, dla której $G$ jest $k$-kolorowalny.

:::

:::::{prf:remark}

1. Graf jest $2$-kolorowalny wtedy i tylko wtedy, gdy jest dwudzielny -- stąd
   $\chi(K_{r,s})=2 .$

2. Dla cyklu $C_n$: $\ \chi(C_n)=2$, gdy $n$ jest parzyste, oraz $\chi(C_n)=3$, gdy
   $n$ jest nieparzyste.

3. Dla grafu pełnego $\chi(K_n) = n .$

::::{container} side-by-side

:::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elemR/.style={draw, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemB/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemG/.style={draw, circle, fill=green!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.4,-1.5) rectangle (1.4,1.5);

  \node[elemR] (v1) at (0, 1) {1};
  \node[elemB] (v2) at (0.87, 0.5) {2};
  \node[elemR] (v3) at (0.87, -0.5) {3};
  \node[elemB] (v4) at (0, -1) {4};
  \node[elemR] (v5) at (-0.87, -0.5) {5};
  \node[elemG] (v6) at (-0.87, 0.5) {6};

  \draw (v1) -- (v2);
  \draw (v1) -- (v4);
  \draw (v1) -- (v6);

  \draw (v2) -- (v3);
  \draw (v2) -- (v5);

  \draw (v3) -- (v4);
  \draw (v3) -- (v6);

  \draw (v4) -- (v5);
  \draw (v4) -- (v6);

  \draw (v5) -- (v6);

\end{tikzpicture}
```

:::

:::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elemR/.style={draw, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemB/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.4,-1.5) rectangle (1.4,1.5);

  \node[elemR] (v1) at (0, 1) {1};
  \node[elemB] (v2) at (0.87, 0.5) {2};
  \node[elemR] (v3) at (0.87, -0.5) {3};
  \node[elemB] (v4) at (0, -1) {4};
  \node[elemR] (v5) at (-0.87, -0.5) {5};
  \node[elemB] (v6) at (-0.87, 0.5) {6};

  \draw (v1) -- (v2);
  \draw (v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v5) -- (v6);
  \draw (v6) -- (v1);

\end{tikzpicture}
```

:::

:::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elemO/.style={draw, circle, fill=orange!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemY/.style={draw, circle, fill=green!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemB/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elemO] (v1) at (0, 1) {1};
  \node[elemY] (v2) at (0.95, 0.31) {2};
  \node[elemB] (v3) at (0.59, -0.81) {3};
  \node[elemO] (v4) at (-0.59, -0.81) {4};
  \node[elemY] (v5) at (-0.95, 0.31) {5};

  \draw (v1) -- (v2);
  \draw (v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v5) -- (v1);

\end{tikzpicture}
```

:::

:::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elemO/.style={draw, circle, fill=orange!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemY/.style={draw, circle, fill=yellow!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemB/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemG/.style={draw, circle, fill=green!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemR/.style={draw, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elemO] (v1) at (0, 1) {1};
  \node[elemY] (v2) at (0.95, 0.31) {2};
  \node[elemB] (v3) at (0.59, -0.81) {3};
  \node[elemG] (v4) at (-0.59, -0.81) {4};
  \node[elemR] (v5) at (-0.95, 0.31) {5};

  \draw (v1) -- (v2);
  \draw (v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v5) -- (v1);
  \draw (v1) -- (v3);
  \draw (v1) -- (v4);
  \draw (v2) -- (v4);
  \draw (v2) -- (v5);
  \draw (v3) -- (v5);

\end{tikzpicture}
```

:::

::::

:::::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:example}

1. {index}`graf; Petersena` **Graf Petersena** zawiera cykle nieparzystej długości (np. pięciokąt
   zewnętrzny), więc **nie jest dwudzielny**, czyli $\chi(G) \geq 3 .$

   Kolorowanie trzema kolorami widać na rysunku, więc

   $$
   \chi(\text{graf Petersena}) = 3.
   $$

2. {index}`graf koła` **Graf koła** $W_5$: cykl $C_5$ na wierzchołkach
   $1,\ldots,5$, do którego dodajemy wierzchołek centralny $0$
   połączony krawędzią z każdym wierzchołkiem $C_5.$

   $W_5$ jest oczywiście **planarny**.

   Jednocześnie $\chi(W_5)=4$:

   - Ponieważ $1,\ldots,5$ tworzą cykl nieparzystej długości, potrzeba
     do jego pokolorowania co najmniej $3$ kolorów, więc $\chi(W_5)\geq 3 .$

     Co więcej, hub $0$ jest połączony z **każdym** wierzchołkiem obwodu,
     więc jego kolor musi różnić się od wszystkich kolorów użytych na
     obwodzie -- na $0$ trzeba użyć
     **czwartego** koloru. Stąd $\chi(W_5)\geq 4 .$

   - Z drugiej strony, $4$-kolorwanie jest łatwe do uzyskania.

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elemB/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemG/.style={draw, circle, fill=green!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemR/.style={draw, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.8,-1.8) rectangle (1.8,1.8);

  \node[elemB] (o1) at (0, 1.3) {0};
  \node[elemG] (o2) at (-1.236, 0.402) {1};
  \node[elemB] (o3) at (-0.764, -1.052) {2};
  \node[elemG] (o4) at (0.764, -1.052) {3};
  \node[elemR] (o5) at (1.236, 0.402) {4};

  \node[elemR] (i1) at (0, 0.65) {9};
  \node[elemR] (i2) at (-0.618, 0.201) {8};
  \node[elemG] (i3) at (-0.382, -0.526) {7};
  \node[elemB] (i4) at (0.382, -0.526) {6};
  \node[elemB] (i5) at (0.618, 0.201) {5};

  \draw (o1) -- (o2);
  \draw (o2) -- (o3);
  \draw (o3) -- (o4);
  \draw (o4) -- (o5);
  \draw (o5) -- (o1);

  \draw (o1) -- (i1);
  \draw (o2) -- (i2);
  \draw (o3) -- (i3);
  \draw (o4) -- (i4);
  \draw (o5) -- (i5);

  \draw (i1) -- (i3);
  \draw (i3) -- (i5);
  \draw (i5) -- (i2);
  \draw (i2) -- (i4);
  \draw (i4) -- (i1);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elemY/.style={draw, circle, fill=yellow!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemB/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemG/.style={draw, circle, fill=green!15, inner sep=0pt, minimum size=9mm, font=\Large},
    elemR/.style={draw, circle, fill=red!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.5,-1.3) rectangle (1.5,1.5);

  \node[elemR] (v1) at (0, 1) {1};
  \node[elemG] (v2) at (0.95, 0.31) {2};
  \node[elemB] (v3) at (0.59, -0.81) {3};
  \node[elemR] (v4) at (-0.59, -0.81) {4};
  \node[elemG] (v5) at (-0.95, 0.31) {5};
  \node[elemY] (h)  at (0, 0) {0};

  \draw (v1) -- (v2);
  \draw (v2) -- (v3);
  \draw (v3) -- (v4);
  \draw (v4) -- (v5);
  \draw (v5) -- (v1);

  \draw (h) -- (v1);
  \draw (h) -- (v2);
  \draw (h) -- (v3);
  \draw (h) -- (v4);
  \draw (h) -- (v5);

\end{tikzpicture}
```

::::

:::::

::::{narration}

Motywacją historyczną teorii kolorowania grafów był **problem czterech barw**:

:::{container} center-text

***Czy każdą mapę polityczną na płaszczyźnie można pokolorować tak, aby kraje sąsiednie
(o wspólnej granicy) miały różne barwy, używając co najwyżej czterech kolorów?***

:::

Mapę taką
przedstawiamy jako graf planarny (kraje -- wierzchołki, wspólna granica -- krawędź),
a pytanie sprowadza się do zbadania jego liczby chromatycznej.

::::

:::{prf:theorem} o czterech barwach

Każdy graf planarny jest $4$-kolorowalny.

:::

:::{prf:remark}

1. Twierdzenie to ma burzliwą historię: postawione zostało w 1852 roku (F. Guthrie),
   błędny dowód opublikował A. Kempe w 1879 roku, a błąd w nim wykryto dopiero w 1890 roku
   (P. Heawood). Poprawny dowód Appla i Hakena z 1976 roku był pierwszym istotnie
   wykorzystującym wspomaganie komputerowe (analizę tysięcy przypadków), co budziło (i wciąż
   budzi) dyskusje na temat statusu takiego dowodu w matematyce.

2. Dowód słabszego twierdzenia o $6$-kolorowalności grafów planarnych
   opiera się na indukcji względem liczby wierzchołków oraz
   na fakcie, że każdy graf planarny ma wierzchołek stopnia co najwyżej $5$ (co wynika
   ze wzoru Eulera).

:::

## Skojarzenia i twierdzenie Halla

::::{narration}

Rozważmy grupę $n$ dziewcząt i grupę $n$ chłopców, gdzie każda dziewczyna zna pewien
podzbiór chłopców. **Problem małżeństw** opera się na pytaniu:

:::{container} center-text

***Czy każdą z dziewcząt można wydać za mąż za jednego ze znanych jej chłopców***

***(tak, aby żaden chłopiec nie poślubił dwóch dziewcząt)?***

:::

Sytuację modelujemy grafem dwudzielnym $G(V_1,V_2)$, gdzie $V_1$ to
zbiór dziewcząt, $V_2$ -- chłopców, a krawędź łączy dziewczynę z chłopcem, jeśli się znają.

::::

:::{prf:definition}

**Skojarzeniem** {index}`skojarzenie` w grafie $G=(V,E)$ nazywamy dowolny zbiór krawędzi
$M \subseteq E$, z których żadne dwie nie mają wspólnego wierzchołka.

Dla $X\subseteq V$, skojarzenie $M$ nazywamy {index}`skojarzenie; nasycające` **$X$-nasycającym**, jeśli każdy wierzchołek zbioru $X$ należy do
pewnej krawędzi z $M .$

Skojarzenie $M$ nazywamy {index}`skojarzenie; pełne` **pełnym**, jeśli jest $V$-nasycające.

:::

:::{prf:remark}

1. Rozwiązanie problemu małżeństw istnieje wtedy i tylko wtedy, gdy w grafie $G(V_1,V_2)$
   istnieje skojarzenie $V_1$-nasycające.

2. Warunkiem koniecznym istnienia takiego skojarzenia jest, aby **każda** grupa $k$
   dziewcząt znała łącznie **co najmniej** $k$ chłopców -- w przeciwnym razie nie dałoby
   się ich wszystkich skojarzyć z różnymi chłopcami.

   Okazuje się, że jest to warunek dostateczny, o czym mówi twierdzenie Halla.

:::

:::{prf:theorem} Halla o małżeństwach

Niech $G(V_1,V_2)$ będzie grafem dwudzielnym.

Dla $A\subseteq V_1$ oznaczmy przez $N(A)\subseteq V_2$ zbiór wszystkich
sąsiadów wierzchołków z $A .$

Wówczas w grafie $G(V_1,V_2)$ istnieje skojarzenie $V_1$-nasycające wtedy i tylko wtedy, gdy

$$
\forall A\subseteq V_1 \quad |N(A)| \geq |A|
$$

(tzw. {index}`warunek Halla` **warunek Halla**).

:::

:::{prf:corollary}

W każdym dwudzielnym grafie **regularnym** istnieje pełne skojarzenie.

:::

:::::{container} side-by-side

::::{container} column-three-fourth

:::{prf:example}

1. **Różne liczności klas.**

   Rozważmy graf $G(V_1,V_2)$ z $V_1=\Set{a,e}$, $V_2=\Set{b,d,h,k}$ i krawędziami $E=\Set{ad,ah,ak,ed,eh} .$

   Mamy $|V_1|=2<4=|V_2| .$

   Warunek Halla jest spełniony dla każdego $A\subseteq V_1 .$

   Istnieje skojarzenie $V_1$-nasycające.

   Twierdzenie Halla nie wymaga równości $|V_1|=|V_2| .$

2. **Wąskie gardło trudne do wykrycia.**

   Rozważmy graf $G(V_1,V_2)$ z $V_1=\Set{a,e,i,o}$, $V_2=\Set{b,d,h,k}$ i krawędziami $E=\Set{ab,ad,eb,ed,ib,id,ob,od,oh,ok} .$

   Pojedyncze wierzchołki i pary z $V_1$ spełniają warunek Halla.

   Dla $A=\Set{a,e,i}$ mamy $|N(A)|=2<3=|A| .$

   Warunek Halla zawodzi. Skojarzenie $V_1$-nasycające nie istnieje.

3. **Graf dwudzielny regularny.**

   Rozważmy graf $G(V_1,V_2)$ z $V_1=\Set{a,e,i}$, $V_2=\Set{b,d,h}$ i krawędziami $E=\Set{ab,be,ed,di,ih,ha} .$

   Każdy wierzchołek ma stopień $2 .$ Graf jest $2$-regularny i dwudzielny.

   Na mocy wcześniejszego wniosku istnieje skojarzenie pełne.

4. **Pełny graf dwudzielny bez jednego skojarzenia doskonałego.**

   **Skojarzeniem doskonałym** nazywamy skojarzenie pełne w grafie z $|V_1|=|V_2|$ -- takie, które jednocześnie nasyca $V_1$ i $V_2 .$

   **Nieporządkiem** $n$-elementowym nazywamy permutację $\pi$ zbioru $\Set{1,\ldots,n}$ bez punktów stałych, tzn. $\pi(k)\neq k$ dla każdego $k .$ Liczbę nieporządków oznaczamy $D_n .$

   Rozważmy graf $G(V_1,V_2)$ z $V_1=\Set{a,e,i,o}$, $V_2=\Set{b,d,h,k} .$ Startujemy od pełnego grafu dwudzielnego $K_{4,4}$ i usuwamy skojarzenie doskonałe $\Set{ab,ed,ih,ok} .$

   Warunek Halla pozostaje spełniony.

   Skojarzenia doskonałe w grafie $G$ odpowiadają bijekcjom $V_1\to V_2$ omijającym usunięte krawędzie -- czyli nieporządkom.

   Jest ich dokładnie $D_4=9 .$

:::

::::

::::{container} column-one-fourth

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.2,-2) rectangle (1.2,2);

  \node[elem] (a) at (-0.7, 0.5) {$a$};
  \node[elem] (e) at (-0.7, -0.5) {$e$};
  \node[elem] (k) at (0.7, 1.5) {$k$};
  \node[elem] (d) at (0.7, 0.5) {$d$};
  \node[elem] (h) at (0.7, -0.5) {$h$};
  \node[elem] (b) at (0.7, -1.5) {$b$};

  \draw (a) -- (d);
  \draw (a) -- (h);
  \draw (a) -- (k);

  \draw (e) -- (d);
  \draw (e) -- (h);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.2,-2.1) rectangle (1.2,2.1);

  \node[elem] (d1) at (-0.7, 1.5) {$a$};
  \node[elem] (d2) at (-0.7, 0.5) {$e$};
  \node[elem] (d3) at (-0.7, -0.5) {$i$};
  \node[elem] (d4) at (-0.7, -1.5) {$o$};
  \node[elem] (c1) at (0.7, 1.5) {$b$};
  \node[elem] (c2) at (0.7, 0.5) {$d$};
  \node[elem] (c3) at (0.7, -0.5) {$h$};
  \node[elem] (c4) at (0.7, -1.5) {$k$};

  \draw (d1) -- (c1);
  \draw (d1) -- (c2);
  \draw (d2) -- (c1);
  \draw (d2) -- (c2);
  \draw (d3) -- (c1);
  \draw (d3) -- (c2);

  \draw (d4) -- (c1);
  \draw (d4) -- (c2);
  \draw (d4) -- (c3);
  \draw (d4) -- (c4);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.2,-1.6) rectangle (1.2,1.6);

  \node[elem] (d1) at (-0.7, 1) {$a$};
  \node[elem] (d2) at (-0.7, 0) {$e$};
  \node[elem] (d3) at (-0.7, -1) {$i$};
  \node[elem] (c1) at (0.7, 1) {$b$};
  \node[elem] (c2) at (0.7, 0) {$d$};
  \node[elem] (c3) at (0.7, -1) {$h$};

  \draw (d1) -- (c1);
  \draw (d1) -- (c2);
  \draw (d2) -- (c2);
  \draw (d2) -- (c3);
  \draw (d3) -- (c3);
  \draw (d3) -- (c1);

\end{tikzpicture}
```

```{tikz}
\begin{tikzpicture}[scale=1.8, >=stealth,
    elem/.style={draw, circle, fill=blue!15, inner sep=0pt, minimum size=9mm, font=\Large}]

  \path (-1.2,-2.1) rectangle (1.2,2.1);

  \node[elem] (a) at (-0.7, 1.5) {$a$};
  \node[elem] (e) at (-0.7, 0.5) {$e$};
  \node[elem] (i) at (-0.7, -0.5) {$i$};
  \node[elem] (o) at (-0.7, -1.5) {$o$};
  \node[elem] (b) at (0.7, 1.5) {$b$};
  \node[elem] (d) at (0.7, 0.5) {$d$};
  \node[elem] (h) at (0.7, -0.5) {$h$};
  \node[elem] (k) at (0.7, -1.5) {$k$};

  \draw (a) -- (d);
  \draw (a) -- (h);
  \draw (a) -- (k);

  \draw (e) -- (b);
  \draw (e) -- (h);
  \draw (e) -- (k);

  \draw (i) -- (b);
  \draw (i) -- (d);
  \draw (i) -- (k);

  \draw (o) -- (b);
  \draw (o) -- (d);
  \draw (o) -- (h);

\end{tikzpicture}
```

::::

:::::