Zadania z matematyki dyskretnej do sprawdzenia #6

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
gardner

Zadania z matematyki dyskretnej do sprawdzenia #6

Post autor: gardner »

1.Twierdzenie Diraca jest najlepsze w swojej klasie, tzn. w założeniu \(\displaystyle{ \delta \ge \frac{p}{2}}\)
liczby \(\displaystyle{ \frac{p}{2}}\) nie można zastąpić mniejszą (to znaczy można,ale otrzyma się fałszywe twierdzenie.

2. Jeśli \(\displaystyle{ \left| V(G)\right| \ge 5}\) i każdy podgraf indukowany w \(\displaystyle{ G}\) przez \(\displaystyle{ 5}\) wierzchołków jest \(\displaystyle{ 2}\)-spójny to \(\displaystyle{ G}\)
ma cykl Hamiltona.

3.\(\displaystyle{ G}\) jest dwuspójny i każdy podgraf indukowany w \(\displaystyle{ G}\) przez \(\displaystyle{ 3}\) wierzchołki ma co najmniej jedna krawędź to \(\displaystyle{ G}\) ma cykl Hamiltona.


2.
Bierzemy dowolny wierzchołek \(\displaystyle{ x}\) grafu \(\displaystyle{ G}\).
Przypuśćmy,że istnieją 3 wierzchołki \(\displaystyle{ z,t,u}\) różne od \(\displaystyle{ x}\) z którymi \(\displaystyle{ x}\) nie sąsiaduje. Wówczas,dla każdego \(\displaystyle{ w \neq x,z,t,u}\) w podgrafie indukowanym przez \(\displaystyle{ \left\{ w,x,z,t,u\right\}}\) \(\displaystyle{ x}\) ma stopień \(\displaystyle{ 1}\) (połączony z w) a więc podgraf ten nie jest dwuspójny. Wiec wierzchołki takie nie istnieją,czyli każdy wierzchołek \(\displaystyle{ x}\),oprócz samego siebie, nie sąsiaduje z co najwyżej dwoma innymi wierzchołkami. Stąd dla każdego \(\displaystyle{ x}\),
\(\displaystyle{ deg(x) \ge p-3}\) a ponieważ \(\displaystyle{ p \ge 5}\),więc \(\displaystyle{ deg(x) \ge \frac{p}{2}}\) i z twierdzenia Diraca mamy cykl Hamiltona.


Proszę o wskazówki do 2 pozostałych i sprawdzenie tego
ODPOWIEDZ