Cykl hamiltona w grafie o 6 wierzchołkach

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

Cykl hamiltona w grafie o 6 wierzchołkach

Post autor: gardner »

Witam,mam takie zadanie.
Mamy graf o p\(\displaystyle{ \ge}\)6 wierzchołkach. Wykazać,że ma cykl hamiltona jeżeli każdy jego podgraf indukowany przez \(\displaystyle{ 4}\) wierzchołki ma \(\displaystyle{ 4}\) krawędzie.-- 29 wrz 2014, o 18:21 --Naprawdę nikt nie ma pomysłu na to zadanie? Nie proszę o rozwiązanie tylko jakąś wskazówkę,sposób postępowania.
kicaj

Cykl hamiltona w grafie o 6 wierzchołkach

Post autor: kicaj »

Pokaż, że ten graf nie zawiera "theta podgrafu".
gardner

Cykl hamiltona w grafie o 6 wierzchołkach

Post autor: gardner »

Ale skąd wiem,że on jest dwuspójny? Myślę,że to zły pomysł,bo nie wiem z jakim grafem mam do czynienia
kicaj

Cykl hamiltona w grafie o 6 wierzchołkach

Post autor: kicaj »

Usuwając dowolny wierzchołek usuwamy tylko krawędzie o końcach w w tym wierzchołku. Usuńmy zatem jakiś wierzchołek \(\displaystyle{ w}\) z grafu \(\displaystyle{ G.}\) Weźmy zatem dowolne dwa wierzchołki \(\displaystyle{ u,v\in G\setminus \{w\}}\) i dobierzmy jeszcze dwa inne wierchołki \(\displaystyle{ s,t\in G\setminus\{w\}.}\) Graf indukowany w \(\displaystyle{ G\setminus \{w\}}\) przez \(\displaystyle{ u,v,s,t}\) jest taki sam jak graf indukowany przez \(\displaystyle{ u,v,s,t}\) w \(\displaystyle{ G}\) zatem ma \(\displaystyle{ 4}\) krawędzie a więc jest spójny, w szcególności istnieje droga łącząca punkty \(\displaystyle{ u}\) i \(\displaystyle{ v}\) w grafie \(\displaystyle{ G\setminus \{w\}}\) a to oznacza, że graf \(\displaystyle{ G}\) jest dwuspójny.
gardner

Cykl hamiltona w grafie o 6 wierzchołkach

Post autor: gardner »

Przeglądam teraz ten post i muszę go odświeżyć. Dalej nie widzę,żeby ten graf był dwuspójny: o dwuspójności znam tylko twierdzenie Airesa i że dla każdej pary wierzchołków musi istnieć cykl prosty. Może ktoś dokończyć to zadanie,ewentualnie pokazać,że ten graf jest na pewno dwuspójny?
ODPOWIEDZ