Twierdzenia Kamil: Mam takie twierdzenia, czy dobrze je rozumiem?: 1.G jest grafem Eulera wtedy i tylko wtedy, gdy każdy jego wierzchołek ma stopień parzysty Moja odpowiedź: Jeśli graf ma jakieś wierzchołki stopnia nieparzystego to nie jest Eulerowski, a jeśli wszystkie są stopnia parzystego, to nie można zdecydować. 2.(Tw. O.Ore) Niech G = (V, E) będzie grafem prostym, w którym każde dwa niesąsiadujące wierzchołki u, v ∊ V spełniają warunek: d(u)+d(v)≥|V| Wówczas G jest grafem hamiltonowskim. Moja odpowiedź: Jeśli graf nie spełnia warunku, to na pewno nie jest hamiltonowski, jeśli spełnia, to nie można rozstrzygnąć. Czy dobrze interpretuję powyższe twierdzenia?

jc: Przecież to to samo. wszystkie wierzchołki mają stopień parzysty = każdy wierzchołek ma stopień parzysty Drugie źle. Jeśli suma ... , to graf jest hamiltonowski. Jeśli nie jest spełniony warunek, to nie wiadomo (faktycznie różnie bywa).

jc: Uwaga do pierwszego punktu. Graf jest grafem eulerowskim ⇔ jest spójny i każdy wierzchołek ma parzysty stopień. Twoja odpowiedź jest prawidłowa, choć zacytowane twierdzenie niezupełnie. Dwa rozłączne trójkąty nie tworzą grafu eulerowskiego.

Kamil: Czyli jak można obalić tezę, czyli udowodnić ze graf NIE jest hamiltonowski?

Pytający: "Czyli jak można obalić tezę, czyli udowodnić ze graf NIE jest hamiltonowski?" Dla założeń przyjętych w twierdzeniu Orego oczywiście nie da się obalić tezy (graf jest hamiltonowski), bo przecież ta teza jest prawdziwa (to twierdzenie jest udowodnione). Dorzucę jeszcze trochę logiki, jeśli: A⇒B // z A wynika B; jeśli A to B jest zdaniem zawsze prawdziwym (udowodnionym twierdzeniem), to: • jeśli A jest prawdziwe, to B jest prawdziwe, • jeśli A jest fałszywe, to nic to nie mówi o B, • jeśli B jest prawdziwe, to nic to nie mówi o A, • jeśli B jest fałszywe, to A jest fałszywe. A to warunek wystarczający, żeby zachodziło B. B to warunek konieczny, żeby zachodziło A. Jeśli: A⇔B // A wtedy i tylko wtedy, gdy B; A jest równoważne z B jest zdaniem zawsze prawdziwym (udowodnionym twierdzeniem), to: • jeśli A jest prawdziwe, to B jest prawdziwe, • jeśli A jest fałszywe, to B jest fałszywe, • jeśli B jest prawdziwe, to A jest prawdziwe, • jeśli B jest fałszywe, to A jest fałszywe. A to warunek konieczny i wystarczający, żeby zachodziło B. B to warunek konieczny i wystarczający, żeby zachodziło A.