---
# System prepended metadata

title: Lista 14
tags: [Matematyka Dyskretna M]

---

###### tags: `Matematyka Dyskretna M`

# Lista 14

## 2
Dowód przeprowadzę przez indukcję po k.
**1$^\circ$** dla k=1
Wtedy mamy 2 wierzchołki połączone krawędzią, co daje jedną ścieżkę.

**2$^\circ$** Załóżmy, że dla k zachodzi, sprawdźmy dla k+1:
Wtedy do każdego wierzchołka dopisujemy jakiś bit 0 lub 1. Inaczej mówiąc z każdego ciągu k-bitowego robimy 2 ciągi k+1-bitowe. Weźmy dwa dowolne wierzchołki i nazwijmy je $v$ i $u$. Rozpatrzmy teraz przypadki:
**1$^\circ$** rozpatrujemy drogi między wierzchołkami $v$ i $u$, które zostały stworzone z jednego ciągu:
wtedy mamy k dróg o długości 3. $v$ jest połączony z wierzchołkiem, który ma różny bit na pozycji innej niż ostatnia, ten jest połączony z kolejnym, który ma inny ostatni bit, a ten jest połączony z $w$.
$k+1$ drogą jest bezpośrednia krawędź między tymi wierzchołkami.

**2$^\circ$** rozpatrujemy drogi między wierzchołkami, które nie zostały stworzone z jednego ciągu:

W przypadku jak mają ostatnie bity różne.
Weźmy z założenia indukcyjnego k-1 dróg rozłącznych, które wyglądają w następujący sposób. Weźmy ostatni bit $v$ i nazwijmy go b. Bit przeciwny będę oznaczał jako ~b. $v$ jest połączone z pierwszym wierzchołkiem drogi z założenia indukcyjnego, następnie jest ona połączona z wierzchołkiem z końcowym bitem równym ~b, który idzie drogą z założenia indukcyjnego
aż do $w$. Mamy więc $k-1$ rozłączonych dróg ostatnie dwie powstają z $k$-tej drogi z założenia inducyjnego. $k$-ta droga to taka, która przechodzi ostatnią drogą z założenia indukcyjnego, która ma ostatni bit równy $b$, a $k+1$ po tej drodze z ostatnimi bitami ~b.

W przypadku gdy mają takie same bity.
$k$ dróg uzyskujemy z założenia indukcyjnego. $k+1$ drogę uzyskujemy przechodząc dowolną z tych ścieżek na przeciwnym końcowym bicie.

Na podstawie indukcji matematycznej pokazałem, że teza zachodzi.
## 3
### a)
Dowód przeprowadzę przez indukcję po k.

**1$^\circ$** dla k=2
Mamy jedną krawędź więc teza zachodzi.

**2$^\circ$** Załóżmy, że dla k zachodzi, sprawdźmy dla k+1:
Dodajemy wierzchołki i łączymy je z sąsiadami, co może dać minimalnie cykl długości 4, więc nie ma możliwości dostania trójkąta, a następnie łączymy nowo powstałe wierzchołki z kolejnym-nowym wierzchołkiem, a wiemy, że między nowo powstałymi wierzchołkami nie było połączeń, więc nie przyczyni się to do powstania trójkąta.

Na podstawie indukcji matematycznej pokazałem, że teza zachodzi.

### b)

Dowód przeprowadzę przez indukcję po k.
**1$^\circ$** dla k=2
Mamy 2 wierzchołki i 2 kolory, co daje możliwość ich pokolorowania.

**2$^\circ$** Załóżmy, że dla k zachodzi, sprawdźmy dla k+1:
Przy tworzeniu $M_{k+1}$ zauważmy, że $v'_i$ łączymy z sąsiadami $v_i$, czyli każdy taki $v'_i$ można pokolorować kolorem $v_i$ (korzystając z założenia indukcyjnego), następnie $w$ kolorujemy nowym kolorem, czyli pokolorwaliśmy $M_{k+1}$ $k + 1$ kolorami.

Na podstawie indukcji matematycznej pokazałem, że teza zachodzi.

## 6
Dodajmy $n-k$ chłopców znanych przez wszystkie dziewczyny. Wtedy z twierdzenia Halla wiemy, że warunkiem koniecznym i dostatecznym aby $n$ dziewczyn (każda dziewczyna) mogło sobie znaleźć męża jest, aby każda podgrupa dziewcząt licząca $r$ osób znała co najmniej $r$ chłopców. Po odjęciu tych $n-k$ chłopców znanych przez wszystkie dziewczyny dostajemy równoważność, że warunkiem koniecznym i dostatecznym, aby $n-(n-k)=k$ dziewczyn mogło sobie znaleźć męża jest, aby każda podgrupa dziewcząt licząca $r$ osób znała co najmniej $r-(n-k)=k+r-n$ chłopców, co należało pokazać.
## 7
Weźmy wszystke wierzchołki chłopców i "rozdzielmy" je na 4 zachowując zasadę, że jak jakaś dziewczyna znała tego chłopca to będzie znała wszystkie 4 wierzchołki tego chłopca. Z twierdzenia Halla wiemy, że warunkiem koniecznym i wystarczającym, aby każda dziewczyna mogła sobie znaleźć męża jest, aby każdy podzbiór tych dziewczyn był $\leq$ liczbie rozdzielonych chłopców, których znają. Po "scaleniu" wierzchołków chłopców równoważne jest zdanie, że warunkiem koniecznym i wystarczającym jest aby każda dziewczyna mogła sobie znaleźć męża, to każdy podzbiór tych dziewczyn musi być $\leq$ liczbie wierzchołków mężczyzn podzielonych przez 4 
($\frac k4$), których znają, co należało pokazać.

## 8
Indukcja po liczbie wierzchołków
**1$^\circ$** 
**dla n=1**
Mamy nieparzystą liczbę wierzchołków, więc pełne skojarzenie nie istnieje.
**dla n=2**
Mamy możliwość położenia tylko jednej krawędzi, co daje pełne skojarzenie.
**2$^\circ$** 
Załóżmy, że dla $n$ teza zachodzi, sprawdźmy dla $n+2$
Weźmy drzewo mające $n+2$ wierzchołków. Weźmy dowolny liść. Jeżeli w takim drzewie istniałoby pełne skojarzenie to musiałby być połączony z rodzicem krawędzią w tym drzewie (w przeciwnym wypadku nie byłoby tam pełnego skojarzenia, więc wtedy teza zachodzi). Po usunięciu liścia i jego rodzica z tezy indukcyjnej wiemy, że jest tam maksymalnie jedno skojarzenie, więc po dodaniu tych dwóch wierzchołków, również będzie tam maksymalnie 1 pełne skojarzenie.

Na podstawie indukcji matematycznej pokazałem, że teza zachodzi.


## 10
Weźmy dowolny podzbiór wierzchołków z jednej grupy wierzchołków w dowolnym grafie dwudzielnym d-regularnym i nazwijmy go $K$. Skoro jest on d-regularny to z każdego wierzchołka tej grupy wychodzi d krawędzi do drugiej grupy oraz każdy wierzchołek z drugiej grupy może "przyjąć" maksymalnie d krawędzi. Zbiór wszystkich wierzchołków, które są połączone bezpośrednio krawędzią z dowolnym wierzchołkiem z $K$ nazwijmy $W$. Zauważmy, że zachodzi nierówność $|W| \geq|K|$. Załóżmy nie wprost, że $|K| > |W|$. Z $K$ wychodzi dokładnie $d\times|K|$ krawędzi do $W$, co daje sprzeczność. Ponieważ $|W|$ może maksymalnie "przyjąć" $d\times |W|$ krawędzi (z założenia $|K| > |W|$). Czyli $|W| \geq|K|$. Z twierdzenia Halla wiemy, że w takim grafie znajduje się pełne skojarzenie, co kończy dowód.

## 11

Weźmy dowolny graf 3-regularny, w którym znajduje się cykl Hamiltona. Z lematu o uściskach dłoni wiemy, że taki graf ma parzystą liczbę wierzchołków. Przejdźmy tym cyklem jednocześnie kolorując każdą krawędź na zmianę kolorami. W taki sposób zużyliśmy dwa kolory i każdy wierzchołek ma po jednej wychodzącej krawędzi. W takiej sytuacji wystarczy, że pokolorujemy te pozostałe na trzeci kolor. Takim sposobem udało się pokolorować krawędzie takiego grafu 3 kolorami.

Nie wystarczą nam 2 kolory, ponieważ w każdym takim grafie z wierzchołków wychodzą 3 krawędzie, więc z zasady szufladkowej Dirichleta musiałyby istnieć takie 2 krawędzie, które mają ten sam kolor, a taka sytuacja nie może się zdażyć.

## 13

Z każdego wierzchołka wychodzi $n-1$ krawędzi, więc indeks chromatyczny musi być $\geq n-1$

Dla $n$ nieparzystego:
Weźmy taki graf i zauważmy i pokolorujmy go minimalną liczbą kolorów. Weźmy podgraf, który zawiera wszystkie wierzchołki i krawędzie pokolorowane jednym kolorem. Zauważmy, że taki graf ma maksymalnie $\lfloor\frac n2\rfloor$ krawędzi. Graf pełny ma krawędzi $\frac{n(n-1)}{2}$. Patrząc, że każdy taki podgraf reprezentuje jeden kolor to taki graf pełny nie można pokolorować mniejszą ilośćią kolorów niż $\frac{n(n-1)}{2\times\lfloor\frac n2\rfloor}=\frac{n(n-1)}{n-1}=n$

Dla dowolnego n:
Pokolorujmy taki graf $n$ kolorami w taki sposób, że pomiędzy wierzchołkiem $v_i$ i $v_k$, jest krawędź
($v_i$,$v_k$) pokolorowana na kolor $i+k$ (jeżeli $i+k \geq n$ to wtedy ta krawędź jest pokolorowana kolorem $i+k-n$).
Wyjątkiem jest kolorowanie krawędzi pomiędzy wierzchołkiem $v_0$. Wtedy
krawędź $(v_0, v_i)$ jest pokolorowana na kolor $2\times i$ (chyba, że jak wyżej $2\times i \geq n$ wtedy na kolor $2\times i - n$)

Czyli dowolny graf $K_n$ można pokolorować $n$ kolorami.

Dla $n$ nieparzystego kończy to dowód.

Dla $n$ parzystego:
Spróbujmy dodać jeden wierzchołek do takiego grafu pokolorowanego wyżej. Zauważmy, że wierzchołek $v_i$ nie jest połączony z żadnym innym wierzchołkiem krawędzią pokolorowaną kolorem $i$. Więc połączmy go z nowo dodanym wierzchołkiem krawędzią pokolorowaną kolorem $i$. Wtedy nowy wierzchołek jest połączony z każdym innym, zachowując zasadę kolorowania krawędzi. Czyli dla $n$ parzystego pokolorowaliśmy taki graf używając $n-1$ kolorów, co kończy dowód.

<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>