# Lista 13

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| X | X | X | X | X | | | | X | X | X | | X | X | |

## Zadanie 1

Załóżmy, że $G$ jest planarny.

Skoro jest planarny to możemy narysować go jako graf płaski (tak, że żadne dwie krawędzie na rysunku się nie przecinają).

Wybierzmy dowolny wierzchołek $v$, a następnie krawędź łączącą $v$ z $v'$ -- $e$. Teraz chcemy ściągnąć $v$ do $v'$.

Wiemy, że żadna z krawędzi, która jest incydenta do $v$ nie przecina się z inną. Możemy zatem wybrać krawędź $e'$ "równoległą" do $e$ (taką, że patrząc na rysunek nie istnieje żadna inna krawędź wychodząca z $v$ pomiędzy $e$ i $e'$.). Bez straty ogólności, przyjmijmy, że znajduje się ona na lewo od krawędzi $e$ na rysunku. Przedłużmy ją do wierzchołka $v'$ tak, aby nie przechodziła przez wierzchołek $v$.

Za każdym razem wybieramy kolejną krawędź po lewej stronie względem poprzedniej. Każdą z nich przedłużamy tak, aby odchylić się od poprzedniej i zakończyć w wierzchołku $v'$.

W ten sposób otrzymamy graf płaski $G \cdot e$. Zatem $G \cdot e$ jest planarny.

---

Graf Petersona


Załóżmy nie wprost, że graf Petersona jest planarny.

Musi zatem spełniać zależność opisaną wzorem Eulera:
$$
n-m+f = 2
$$

Graf Petersona ma $10$ wierzchołków $15$ krawędzi. Skoro tak to ze wzoru Eulera wynikałoby, że musi mieć $7$ ścian. Najmniejszy cykl w grafie Petersona wynosi $5$. Stąd jego ściany musiałyby być co najmniej pięciokątami.

$7$ pięciokątów ma $35$ krawędzi. Każda użyta jest przy ograniczaniu dokładnie dwóch ścianach. Stąd graf Petersona musiałby mieć co najmniej $35/2 \approx 17$ krawędzi. Sprzeczność.

---

## Zadanie 2

**Lemat**:
> Jeśli w grafie $G$ zachodzi $m(G) > 3n(G) - 6$ to $G$ jest nieplanarny.

Dowód lematu:

$1^\circ$ $G$ jest spójny.
Załóżmy niewprost, że $G$ jest planarny. Każdy graf planarny spełnia $m(G) \leq 3n(G) - 6$. Sprzeczność.

$2^\circ$ $G$ nie jest spójny.
Załóżmy nie wprost, że $G$ jest planarny.
Skoro $G$ jest planarny, to każda jego składowa spójna $H_1,H_2,...,H_k$ jest planarna. Każda z nich spełnia $m(H_i) \leq 3n(H_i) - 6$.

Jeśli zsumujemy wszystkie nierówności otrzymamy:

$$
m(H_1) + m(H_2) + ... + m(H_k) \leq 3(n(H_1) + n(H_2) + ... + n(H_k)) - 6k \\
m(G) \leq 3n(G) - 6k \leq 3n(G) - 6
$$

Sprzeczność.

---

Dowód twierdzenia:
Ponieważ $G$ i $\stackrel{-}{G}$ tworzą klikę to suma ich krawędzi to

$$
m(G) + m(\stackrel{-}{G}) = \frac{n(n-1)}{2}
$$

Zatem jeden z nich musi mieć co najmniej $\frac{n(n-1)}{4}$ krawędzi.

Wiemy, że $n \geq 11$. Spełniona jest zatem nierówność (równa $0$ dla $\approx 2.23$ i $\approx 10.77$):
$$
n^2 -13n + 24> 0\\
n^2 -n > 12n - 24\\
\frac{n(n-1)}{4} > 3n - 6 \\
m > 3n - 6
$$

Zatem co najmniej jeden z tych grafów jest nieplanarny.

---

</br>

## Zadanie 3
**Lemat**:
> Jeśli w grafie $G$ zachodzi $m(G) > 3n(G) - 6$ to $G$ jest nieplanarny.

$G$ -- graf prosty planarny o co najmniej trzech wierzchołkach.
Lemat o uściskach dłoni:

$$
2m = \sum_v deg(v)
$$

Załóżmy nie wprost, że w $G$ istnieją maksymalnie $2$ wierzchołki stopnia niewiększego niż $5$.
Oszacujmy od dołu liczbę krawędzi w tym grafie.

$$
\sum_v deg(v) \geq 6 \cdot (n(G)-2) + 0 = 6n(G) - 12 \\
2m(G) \geq 6n(G) - 12 \\
m(G) \geq 3n(G) - 6 \\
$$

Weźmy graf $G$ i utwórzmy $G'$ odejmując wierzchołki stopnia zerowego.

$$
m(G) \geq 3n(G) - 6 = 3(n(G) - 2) = 3n(G') > 3n(G') - 6
$$

Sprzeczność, bo skoro $G$ jest planarny to $G'$ też musi być planarny.

## Zadanie 4

Niech $G$ -- graf płaski.

Jeśli $G$ jest płaski to każda jego składowa spójności $H_1,H_2,...,H_t$ jest płaska. Każda spełnia wzór Eulera

$$
n(H_i)-m(H_i) + f(H_i) = 2
$$

Sumując wszystkie równania otrzymamy:

$$
n(H_1) + n(H_2) + ... + n(H_t) - (m(H_1) + m(H_2) + ... + m(H_t)) + f(H_1) + f(H_2) + ... + f(H_t) = 2t\\
n(G) - m(G) + f(G) + t -1 = 2t \space \space (*)\\
n(G) + f(G) = t + m(G) + 1 \\
n(G) + f(G) = k(G) + m(G) + 1\\
$$

$(*)$ Ściana zewnętrzna została zsumowana $t$ razy.

## Zadanie 5

Niech $G$ -- spójny graf płaski, w którym najmniejszy cykl ma długość $r$.

Każda ściana grafu $G$ musi być ograniczone co najmniej $r$ krawędziami. Zatem $G$ musi składać się z co najmniej $\frac{f \cdot r}{2}$ krawędzi.

$$
m \geq \frac{f \cdot r}{2}
$$

Ze wzoru Eulera $n - m + f = 2 \implies f =2 + m - n$:

$$
2m \geq (2 + m - n) \cdot r \\
2m \geq 2r + mr - nr \\
m(2 - r) \geq r(2 - n) \\
m(n-2) \leq r(n-2) \\
$$

Równość zachodzi dokładnie wtedy, gdy każdą ścianę odgradza dokładnie $r$ krawędzi.

## Zadanie 9

Niech $G$ -- eulerowski graf płaski.

Aby pokazać, że ściany $G$ można pokolorować dwoma kolorami na każdej ścianie stwórzmy graf dualny do $G$ -- $G^*$.

Otrzymywanie grafu dualnego $G^*$:
1. Z każdej ściany grafu $G$ wybieramy po jednym punkcie. Tak wybrane punkty tworzą zbiór wierzchołków $V^*$.
2. Jeśli krawędź $e$ po jednej stronie sąsiadowała ze ścianą $f_1$, a po drugiej z $f_2$ to w grafie $G^*$ odpowiadające ścianom $f_1,f_2$ wierzchołki $v_1^*,v_2^*$ łączymy krawędzią $v_1^*v_2^*$ przecinającą tylko krawędź $e$. Tak wybrane krawędzie tworzą zbiór $E^*$.

Teraz możliwość pokolorowania ścian w grafie $G$ będzie równoważna z możliwością pokolorowania wierzchołków w grafie $G^*$.

---

**Lemat 1**
> Jeśli $G$ -- planarny graf spójny oraz $G^*$ -- graf dualny do $G$ to $G^{**}$ dualny do $G^*$ jest izomorficzny z $G$.

Dowód **lematu 1**:

Zauważmy, że każdy wierzchołek z $G$ odpowiada dokładnie jednej ścianie w $G^*$. Natomiast każda ściana w $G^*$ odpowiada dokładnie jednemu wierzchołkowi w $G^{**}$.

Weźmy dowolne dwa sąsiednie wierzchołki z grafu $G$ i nazwijmy je $u,v$. Wiemy, że odpowiadają one ścianom $f_u^*, f_v^*$ w grafie $G^*$. Skoro $u,v$ są połączone krawędzią to ściany $f_u^*,f_v^*$ mają wspólną krawędź.

Jeśli ściany $f_u^*,f_v^*$ mają wspólną krawędź to wierzchołki $u^{**},v^{**}$, które odpowiadają tym ścianom będą połączone krawędzią.

Zatem wierzchołki $u,v$ przy przekształceniach z $G$ do $G^{**}$ przechodzą na wierzchołki $u^{**},v^{**}$ w $G^{**}$ oraz jeśli $u,v$ są sąsiadujące w $G$ to również sąsiadują w $G^{**}$.

---

**Lemat 2**
> Graf dualny do planarnego grafu eulerowskiego jest dwudzielny.

Dowód lematu:
Niech $G$ -- planarny graf eulerowski, $G^*$ graf dualny do $G$.

Jeśli $G$ jest spójny:
Załóżmy nie wprost, że $G^*$ nie jest dwudzielny. Zatem posiada co najmniej jeden cykl długości nieparzystej. Jeśli weźmiemy graf dualny do $G^*$ -- $G^{**}$ to oznacza, że istnieje tam wierzchołek stopnia nieparzystego. Z **lematu 1** graf $G^{**}$ jest izomorficzny z $G$. Sprzeczność, gdyż $G$ jest grafem eulerowskim, więc stopień każdego wierzchołka w tym grafie jest parzysty.

Jeśli $G$ nie jest spójny:
Ponieważ $G$ jest eulerowski to istnieją w $G$ istnieje co najmniej jeden wierzchołek stopnia $0$. Wierzchołki te leżą zatem w obrębie jakiejś ściany w $G$.

Postępując zgodnie z zasadami konstrukcji grafu dualnego, otrzymamy graf dualny dla grafu będącego grafem $G$ bez wierzchołków zerowego stopnia. Dlatego, że dla takich wierzchołków nie utworzymy ani wierzchołka, ani krawędzi w $G^*$.

Zatem wystarczy rozważyć graf $G$ wykluczając wierzchołki $0$ stopnia, który jest spójny.

---

Z **lematu 2** wiemy, że graf $G^*$ jest dwudzielny, więc możemy pokolorować go dwoma kolorami.
Zatem można pokolorować ściany grafu $G$ dwoma kolorami.

## Zadanie 10

Zauważmy, że do jednej monety może być przystających maksymalnie $6$ monet.

Weźmy zatem skrajnie lewą monetę na płaszyźnie. Jeśli istnieje więcej niż jedna taka moneta, weźmy tą, która jest najwyżej.
Taka moneta może mieć maksymalnie $3$ sąsiadów.



Odłóżmy tą monetę na stos i rekurencyjnie pokolorujmy resztę grafu (używając 4 kolorów).

Skoro wszyscy sąsiedzi tej monety zostali pokolorowani, oznacza to, że pozostał jeden kolor, którym możemy pokolorować odłożoną monetę.

Dlaczego nie zawsze możemy pokolorować trzema kolorami:


Rozłóżmy monety po okręgu "trójkami", czyli że środek pierwszej monety leży na obwodzie dużego koła, a kolejne dwie monety styczne do monety pierwszej leżą na kole tak, że punkt, w którym są styczne (druga z trzecią) leży na okręgu. Pokolorujmy je zaczynając od pierwszej monety z lewej z czarną kropką.

Wystarczy dobrać promień dużego okręgu tak, aby ostatnia moneta, która jest styczna do początku musiała być pokolorowana na kolor $1$.

## Zadanie 11


Pokażmy równoważnie $P_{G•e}(k) + P_G(k) = P_{G \setminus e}(k)$.

Niech $e$ będzie krawędzią łączącą wierzchołki $u$ i $v$.

Rozróżniamy dwa typy kolorowania w $G \setminus e$

$1^\circ$ Jeśli $u,v$ mają taki sam kolor to identyfikując je dostajemy poprawne kolorowanie w grafie $G•e$.

$2^\circ$ Jeśli $u,v$ są różnego koloru to otrzymamy poprawne kolorowanie w $G$.

Co należało pokazać.

## Zadanie 13

Jeśli $\chi(G) = 1$ to w grafie nie może być żadnej krawędzi (inaczej nie moglibyśmy pokolorować jej na jeden kolor).

Wpp.
Weźmy dowolne kolorowanie grafu $G$ $\chi(G)$ kolorami.
Pomiędzy każdymi dwoma zbiorami wierzchołków o tym samym kolorze musi istnieć krawędź (inaczej moglibyśmy pokolorować je na ten sam kolor).

Zatem $\binom{\chi(G)}{2} = \frac{\chi(G) \cdot (\chi (G) - 1)}{2}$

Co należało pokazać.

## Zadanie 14

Niech $\chi(G) = k$.
Wtedy $V(G)$ może być podzielony na $k$ zbiorów takich, że żadnych dwóch wierzchołków w danym grafie nie łączy krawędź.

Pośród tych zbiorów musi istnieć zbiór $X$, który zawiera co najmniej $\frac{n}{k}$ wierzchołków.

Ale $X$ tworzy graf pełny w $\stackrel{-}{G}$, zatem $\chi(\stackrel{-}{G}) \geq \frac{n}{k}$

Mamy zatem $\chi(G) \cdot \chi(\stackrel{-}{G}) \geq k \cdot \frac{n}{k} = n$

###### tags: `mdm`