Lista 13 - HackMD

###### tags: `Matematyka Dyskretna M` # Lista 13 ## 1 Weźmy dowolny graf planarny i nazwijmy go $G$. Jeżeli ten graf nie jest spójny to wtedy $G$ niech będzie jego dowolną spójną składową. Rozpatrzmy teraz jego przedstawienie w postaci grafu płaskiego. Zauważmy, że przy "przesunięciu" jednego wierzchołka do drugiego (przy identyfikacji końców krawędzi łączącej te wierzchołki) nie będzie sytuacji, że krawędzie wychodzące z tych wierzchołków się przetną (Można to sobie rozrysować w takiej postaci, że jak mamy jeden wierzchołek, to można "rozdzielić" go na 2 wierzchołki i podzielić między nimi krawędzie w taki sposób, że one na pewno nie będą się przecinać), czyli po zabraniu tej krawędzi można przedstawić taki graf jak graf płaski, czyli ten graf jest planarny. Co kończy dowód. Weźmy graf Petersena. ![](https://i.imgur.com/22FA1b4.png) Jest on spójny, mamy w nim 10 wierzchołków, 15 krawędzi, 12 obszarów. Z twierdzenie Eulera wiemy, że jeśli graf jest planarny to $n(G) - m(G) + f(G) = 2$. Inaczej mówiąc, Jeśli $n(G) - m(G) + f(G) \neq 2$ to graf nie jest planarny. $n(G)=10, m(G)=15, f(G)=12$, $10-15+12=7 \neq 2$ czyli graf Petersena nie jest planarny co nalezało pokazać. ## 2 Wiemy, że $G + \hat{G}$ jest grafem pełnym, który ma $\frac{n(n-1)}{2}$ krawędzi. Wiemy również, że jeżeli $G$ oraz $\hat{G}$ jest grafem planarnym to (dla liczby wierzchołków $\geq 3$) $E(G) \leq 3V(G)-6$ oraz $E(\hat{G}) \leq 3V(\hat{G})-6$ Z tego wynika, że $E(G) + E(\hat{G}) \leq 3V(G)-6 + 3V(\hat{G})-6 = 3V(G) + 3V(\hat{G})-12 \leq 6V(G)-12$ Czyli mamy następującą nierówność $\frac{n(n-1)}{2} \leq 6n-12$ $n(n-1) \leq 12n-24$ $n^2-n-12n-24 \leq 0$ $n^2-13n-24 \leq 0$ $n_1=\frac{13+\sqrt{73}}{2} \approx 10,77$ $n_2=\frac{13-\sqrt{73}}{2} \approx 2,23$ Czyli dla $n\in<\frac{13-\sqrt{73}}{2}, \frac{13+\sqrt{73}}{2}>$ (patrząc na założenie, że $V(G) \geq 3$ oraz, że $n\in\mathbb{N}$) $n\in<3, 11)$ Czyli nie istnieje taki graf planarny G, dla którego $V(G) \geq 11$ oraz $\hat{G}$ byłby również planarny, co kończy dowód. ## 3 Weźmy dowolny graf planarny. Wiemy, że w takim grafie zachodzi (dla $V(G) \geq 3$) $m \leq 3n-6$, czyli $2m \leq 6n-12$ i załóżmy nie wprost, że istnieje $<3$ wierzchołków stopnia maksymalnie 5. Rozpatrzmy 3 przypadki **1$^\circ$** Nie ma takich wierzchołków Wetdy $\forall_{v\in V(G)}\space deg(v) \geq6$ czyli $\displaystyle\sum_{v\in V(G)} deg(v) \geq 6n$ Z lematu o uściskach dłoni $\displaystyle\sum_{v\in V(G)} deg(v) = 2m$ Dostajemy $2m \geq 6n$, ale wiemy też, że $2m \leq 6n-12$ więc $6n \leq 2m \leq 6n-12$ $6n \leq 6n - 12$ $0 \leq -12$ Sprzeczność **2$^\circ$** Istnieje 1 taki wierzchołek (nazwijmy go $v_0$) Wetdy $\forall_{v\in V(G)/v_0}\space deg(v) \geq6$ czyli $\displaystyle\sum_{v\in V(G)} deg(v) \geq 6n - 6$ Z lematu o uściskach dłoni $\displaystyle\sum_{v\in V(G)} deg(v) = 2m$ Dostajemy $2m \geq 6n-5$, ale wiemy też, że $2m \leq 6n-12$ więc $6n-6 \leq 2m \leq 6n-12$ $6n-6 \leq 6n - 12$ $-6 \leq -12$ Sprzeczność **3$^\circ$** Istnieją 2 takie wierzchołki (nazwijmy je $v_0$ i $v_1$) Wetdy $\forall_{v\in V(G)/\{v_0 \cup v_1\}}\space deg(v) \geq6$ czyli $\displaystyle\sum_{v\in V(G)} deg(v) \geq 6n - 12$ Z lematu o uściskach dłoni $\displaystyle\sum_{v\in V(G)} deg(v) = 2m$ Dostajemy $2m \geq 6n-12$, ale wiemy też, że $2m \leq 6n-12$ więc $6n-12(suma\space stopni\space wierzchołków) \leq 2m \leq 6n-12$ Możemy zauważyć, że w każdym przypadku taka nierówność jest sprzeczna poza sytuacją, w której ta suma jest dokładnie równa $6n - 12$. Jedyna sytuacja, w której to może się zdarzyć jest taka, kiedy 2 wierzchołki nie mają wychodzących krawędzi, a pozostałe wierzchołki mają ich dokładnie po 6. Żeby taki graf był planarny to jego każda spójna składowa musiałaby być planarna. Jedna z tych spójnych składowych jest regularna stopnia 6. Z podpunktu 1 tego rozwiązania wiemy, że taki graf nie moze być planarny (dochodzimy tam do sprzecznośći). W każdym przykładzie dostaliśmy sprzeczność, co kończy dowód. ## 4 Dowód przeprowadzę przez indukcję po spójnych składowych k. **1$^\circ$** dla k(G)=1 Ze wzoru Eulera wiemy, że n(G) - m(G) + f(G) = 2 Czyli n(G) + f(G) = m(G) + 2 Czyli n(G) + f(G) = m(G) + 1 + 1 **2$^\circ$** Załóżmy, że n(G) + f(G) = m(G) + k(G) + 1 zachodzi, sprawdźmy dla k+1: Weźmy taki graf i nazwijmy go $G_0$. Weźmy dowolną spójną składową $G_0$ i nazwijmy ją $G_{0s}$. Wtedy z bazy indukcji wiemy, że w takim grafie zachodzi $n(G_{0s}) + f(G_{0s}) = m(G_{0s}) + 2$ czyli $n(G_{0s}) + f(G_{0s}) - m(G_{0s}) = 2$ Weźmy graf $G_0 / G_{0s}$ i nawzijmy go $G_1$. Wiemy, że ma on k spójnych składowych, więc z założenia indukcyjnego $n(G_1) + f(G_1) = m(G_1) + k(G_1) + 1$ czyli $n(G_1) + f(G_1)- m(G_1) = k(G_1) + 1$ Pamiętając, że przy dodaniu ilośći obszarów grafu $G_1$ i do $G_{0s}$ musimy odjąć 1 obszar, ponieważ obszar zewnętrzny zostałby policzony podwójnie. Wtedy $n(G_0) + f(G_0) - m(G_0)=$ $=n(G_{0s}) + f(G_{0s}) - m(G_{0s}) + n(G_1) + f(G_1)- m(G_1) - 1=$ $=2 + (k(G_1) + 1) - 1=k(G_1)+2$ Czyli $n(G_0) + f(G_0) - m(G_0)=k(G_1)+2$ $n(G_0) + f(G_0) = m(G_0) + k(G_1)+2$ Na podstawie indukcji matematyczniej pokazałem, że teza zachodzi. ## 5 Weźmy dowolny graf spójny płaski z cyklem i zauważmy, że każda ściana (poza zewnętrzną, która "przylega") jest "otoczona" przez cykl. Więc każda taka ściana ma tyle "boków", ile wynosi długość tego cyklu. Zachodzi więc własność, że dla każej ściany, długość jej boków jest $\geq r$. Każdy bok (krawędź) może maksymalnie rozdzielać 2 obszary, czyli w takim grafie może być maksymalnie $2m$ "boków". Czyli $f\times r \leq 2m$. Z twierdzenia Eulera wiemy, że n - m + f = 2. Wtedy $f = m - n + 2$ $r\times f=r\times m - n\times r + 2r$ Wiemy, że $f\times r \leq 2m$ czyli $r\times m - n\times r + 2r \leq 2m$ $r\times m - n\times r + 2r - 2m \leq 0$ $r(2-n) + m(r-2) \leq 0$ $m(r-2) \leq r(n-2)$ Co trzeba było wykazać. Aby zamiast nierówności była równość, to $f\times r=2m$ ## 11 Rozpatrzmy graf $P_{G / e}(k)$ i mamy dwie opcje pokolorowania go. **1$^\circ$** Na końcach e znajdują się różne kolory Wtedy liczba pokolorowań tego grafu k kolorami jest równa $P_G(k)$ Ponieważ w tym przypadku te kolory muszą być różne. **2$^\circ$** Na końcach e znajdują się te same kolory Wtedy liczba pokolorowań tego grafu k kolorami jest równa $P_{G\bullet e}(k)$ Ponieważ w tym przypadku robimy identyfikację końców krawędzi $e$, co powoduje, że będzie to jeden "scalony wierzchołek", który jest pokolorowany jednym kolorem. Czyli $P_{G / e}(k) = P_G(k) + P_{G\bullet e}(k)$ Z czego otrzymujemy $P_G(k) = P_{G / e}(k) - P_{G\bullet e}(k)$ co należało pokazać. ## 13 Weźmy dowolny graf i pokolorujmy go minimalną liczbą kolorów. Wtedy możemy zauważyć, że dla dowolnych dwóch różnych kolorów $k_1$ i $k_2$ zachodzi własność, że 2 wierzchołki pokolorwane na te 2 kolory są ze sobą połączone bezpośrednio krawędzią (Jakby było inaczej, to wtedy ten graf można byłoby pokolorować mniejszą ilością kolorów, ponieważ wszystkie wierzchołki pokolorowane na $k_2$ możnaby było pomalować na $k_1$). Skoro każdy kolor jest połączony krawędzią bezpośednio z innym kolorem, to wiemy, że krawędzi w tym grafie jest co najmniej $\binom{_X(G)}{2} = \frac{_X(G)\times (_X(G)-1)}{2}$ co należało udowodnić.