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

# Lista 11

## 2
Implikacja w obie strony
**1$^\circ$** $\implies$
Ten graf jest izomorficzny ze swym dopełnieniem. Z tego wynika, że graf ten musi mieć dokładnie połowę krawędzi grafu pełnego, czyli $E(G) = \frac{n(n-1)}{4}$. Skoro jest to liczba krawędzi to musi ona być naturalna, z tego wynika, że $n(n-1)$ musi być podzielne przez $4$. Czyli n % 4 = 0 lub n - 1 % 4 = 0, czyli n % 4 = 0 lub n % 4 = 1

**1$^\circ$** $\impliedby$

Skoro n % 4 = 0 lub n % 4 = 1 rozpatrzmy 2 przypadki

**1$^\circ$** n % 4 = 0
Czyli możemy "podzielić" nasze wierzchołki w 4 równe grupy (zawierające tyle samo wierzchołków) i krawędzie ustawić odpowiednio tak, że 2 grupy będą podgrafami pustymi, a dwie pozostałe pełnymi, oraz będą one połączone jak na rysunku poniżej.

Dopełnieniem takiego grafu jest narysowany niżej graf izomorficzny.

Czyli dla n % 4 = 0 znaleźliśmy taki graf.

**1$^\circ$** n % 4 = 1

Podobnie jak wyżej "dzielimy" nasz graf na 4 równe grupy oraz jeden wierzchołek nazwany A. Narysujmy taki graf, w którym dwie pierwsze grupy są puste a pozostałe pełne, które są połączone tak jak niżej na rysunku.

DOpełnienie tego grafu jest izomorficzne.

Czyli dla n % 4 = 1 znaleźliśmy taki graf.

Co kończy dowód.

## 7

Tę sytuację można zilustrować na grafie.
Każdy wierzchołek musi być połączony z każdym innym (daje nam to graf pełny).
Musimy utworzyć ciąg liczb, w którym ostatnia liczba jest traktowana jako sąsiednia z pierwszą. W grafie możemy to potraktować jako cykl. Każda liczba musi sąsiadować z każdą inną w ciągu dokłądnie raz, co możemy zamienić na problem, czy w danym pełnym grafie znajduje się taki cykl, który każdą krawędź odwiedzi dokładnie raz. Jest to cykl eulerowski. Taki cykl znajduje się w każdym grafie, w którym wszystkie wierzchołki mają stopień parzysty.
W naszej sytuacji stanie się tak, gdy liczba wierzchołków nie licząc jednego jest parzysta. Czyli patrząc na wszystkie wierzchołki musi być ich nieparzysta ilość. Czyli taki ciąg na kole można utworzyć wtedy, kiedy jest ich nieparzyśćie.

Czyli n = 2k + 1, gdzie $k\in\mathbb{N}$

## 8

Weźmy wierzchołek, który ma najwyższy stopień (patrząc tylko na krawędzie wychodzące) i nazwijmy go A. Wtedy do co najmniej połowy pozostałych wierzchołków można z A dojść w 1 ruchu. Teraz weźmy dowolny wierzchołek, do którego nie można dojść w 1 ruchu z A i nazwijmy go B. Wtedy, aby można było dojść do B w 2 ruchach, musiałaby istnieć krawędź przychodząca do B z dowolnego wierzchołka połączonego z A. Musi tak być, w przeciwnym wypadku, z B musiałoby wychodzić tyle samo krawędzi co z A plus jedna (ta, która prowadzi z B do A), co daje sprzeczność (z założenia mojego A ma najwyższy stopień, patrząc tylko na krawędzie wychodzące). Czyli zawsze istnieje z wierzchołka A droga długośći maksymalnie 2 do innych wierzchołków. Czyli taki wierzchołek istnieje, co kończy dowód.

## 9
Indukcja po ilośći wierzchołków.

**1$^\circ$** dla n = 1
Teza jest oczywista.

**2$^\circ$** załóżmy, że teza zachodzi dla n. Sprawdźmy dla n+1

Dokładamy kolejny wierzchołek (nazwijmy go A) i zauważmy, że jak będzie on miał krawędź przychodzącą z ostatniego wierzchołka naszej ścieżki z tezy kroku indukcjnego to wystarczy przedłużyć naszą ścieżkę właśnie o wierzchołek A i wtedy teza będzie zachodzić dla n+1. Jeżeli ta krawędź do A będzie odchodząca do ostatniego wierzchołka naszej ścieżki to rozpatrzmy krawędź do przedostatniego wierzchołka naszej ścieżki. Jeżeli będzie ona przychodzić do A od tego wierzchołka, to można będzie go "dorzucić" do naszej ścieżki tak jak na rysunku poniżej.
Wetdy teza zachodzi. Możemy tak sprawdzać aż do pierwszego wierzchołka (za każdym razem patrząc od końca naszej ścieżki krawędzie muszą odchodzić z A). Czyli wiemy, że jak byłaby jakakolwiek krawędź przychodząca do A to teza zajdzie. Teraz rozpatrzmy przypadek jak każda krawędź z A będzie odchodząca. Wtedy A traktujemy jako początek nowej ścieżki Hamiltona i "dołączamy" ją jako początek. Wtedy ścieżka będzie wyglądała jak na rysunku.
Czyli teza zachodzi dla n+1 wierzchołków.

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

## 10
Jest to możliwe w podanej sekwencji
### Możliwe jest, aby konik wrócił na to samo pole?

Nie, ponieważ musiałby wrócić w 26 ruchu, a skoro zaczynał na konkretnym kolorze (załóżmy że na czarnym), to ostatni ruch (26) musiałby być na kolor przeciwny (w naszym przypadku na kolor biały).

## 12

Weźmy dowolny graf, w którym n = |V(G)| > 3 i dla dowolnych trzech wierzchołków u,v,w istnieją co najmniej dwie spośród trzech krawędzi {u,v}, {v,w}, {w,u}.

Wtedy z twierdzenia Orego wiemy, że jeżeli w grafie dla dwóch niepołączonych bezpośrednio krawędzią wierzchołków (v, u) zachodzi $deg(v) + deg(u) \geq n$ wtedy w takim grafie znajduje się cykl Hamiltona.

Więc dla grafu z zadania weźmy dowolną taką parę niepołączonych bezpośrednio krawędzią wierzchołków (u, v). Jeżeli taka para nie istnieje to założenie twierdzenia Orego zachodzi, więc graf taki ma cykl Hamiltona. Skoro u i v nie są połączone bezpośrednio krawędzią to z zadania każdy inny punkt w grafie jest połączony zarówno z u jak i z v (Jak weźmiemy dowolny taki punkt (nazwijmy go w) to mamy 3 punkty u, v i w. Z założenia, jeżeli nie istnieje krawędź łączaca bezpośrednio u z v to musi istnieć krawędź łącząca u z w oraz v z w). Czyli wierzchołek u musi być połączony z każdym punktem poza v, tak samo jak wierzchołek v (w tym przypadku musi być połączony z każdym nie licząc u). Czyli mamy $deg(v) = deg(u) = n - 2$. Czyli $deg(v) + deg(u) = 2n - 4$. Z zadania $n \geq 4$ a dla takiego warunku $2n-4 \geq n$ czyli $deg(v) + deg(u) \geq n$. Z twierdzenia Orego wiemy, że w takim grafie musi istnieć cykl Hamiltona co kończy dowód.

## 14
Weźmy dowolne n i narysujmy graf $K_{2n}$ (weźmy przykładowe rysunki takich grafów dla n = 2 oraz n = 3)
Zaczynamy w dowolnym wierzchołku i idziemy "zygzakiem" po każdym wierzchołku.
Dla przykładu dla n=2 kolorem czerwonym zaczynamy w lewym górnym rogu, idziemy w prawo, poźniej na skos na lewo i na prawo. Następnie kolorem niebieskiem zaczynamy w następnym punkcie idąc zgodnie z ruchem wskazówek zegara i wykonujemy identyczne kroki. Robimy tak dopóki nie narysujemy $n$ dróg. $n+1$ droga byłaby identyczna jak pierwsza (w tym przypadku jakbyśmy chcieli narysować trzecią drogę pokryłaby się ona z czerwoną). W takiej sytuacji narysujemy zawsze $n$ dróg Hamiltona w takim grafie.
Tak wyglądałby graf dla $n = 3$.

W przypadku grafów $K_{2n+1}$ na chwilę "odkładamy" dodatkowy wierzchołek i rysujemy tak jak wyżej n dróg Hamilotna. (rysunek poniżej dla n = 2)


Teraz zobaczmy, że każda droga narysowana zaczyna się jak i kończy w innym wierzchołku. Wystarczy teraz tylko połączyć początek, jak i koniec każej drogi z tym punktkem, przez co dostaniemy n cykli Hamiltona krawędziowo rozłącznych. (rysunki poniżej dla n = 2 i dla n = 3)


## 15
Weźmy taki graf prosty, który dla każdej pary niesąsiednich wierzchołków u,v deg(u) + deg(v)≥n(G)−1.

Do grafu G dodajmy wierzchołek (w') i połączmy go ze wszystkimi wierzchołkami w tym grafie (nazwijmy nowo powstały graf G'). W wyniku takiej operacji każdy wierzchołek w grafie G' będzie miał zwiększony stopień o 1. Weźmy teraz dowolną parę niesąsiednich wierzchołków u',v'. Z założenia zadania wiemy, że początkowo była spełniona zależność deg(u) + deg(v)≥n(G)−1. Po dodaniu obustronnie liczby 2 otrzymamy:
$deg(u) + 1 + deg(v) + 1 \geq n(G) + 1$
Możemy zauważyć, że $n(G) + 1 = n(G')$ oraz $deg(u) + 1 + deg(v) + 1 = deg(u') + deg(v')$
Z tego mamy nierówność $deg(u') + deg(v') \geq n(G')$

Z twierdzenia Orego wiemy, że w grafie G' znajduje się cykl Hamiltona. Nazwijmy wierzchołki, które w cyklu Hamiltona połączone są krawędzią z w' ($w_1$, $w_2$). Wtedy po usunięciu tego wierzchołka (powrót do grafu G) zauważmy, że od $w_1$ do $w_2$ będzie droga Hamiltona, co należało udowodnić.