D-d ze nie ma drogi prostej w grafie

[filip.wroc]

Moje zadanie brzmi:

1.Czy jest możliwe, by owad poruszający się wzdłuż krawędzi sześcianu przeszedł każdą krawędź dokładnie raz?

Wiem, ze jezeli zbudujemy z wierzcholkow szescianu graf, ktorego krawedziami beda krawedzie szescianu, to dostaniemy graf cykliczny, nieskierowany. Zadanie sprowadza sie do okreslenia czy istnieje w nim droga prosta. Dodatkowo mozna powiedziec, ze graf ma 8 wierzcholkow, z kazdego z nich wychodza dokladnie 3 krawedzie, krawedzi w sumie jest 12.

WIDZE ze takiej nie ma. Ale jak to udowodnic? Ma ktos pomysl? Bo ja nie umiem ugrysc.

Moznaby probowac nie-wprost, najprosciej.
Wiec zakladamy, ze istnieje taka droga prosta.
Czyli istnieje taki ciag krawedzi, ktory ma dlugosc 12 i nie ma powtorzen.
I co dalej? Nie umie tutaj okreslic tej sprzecznosci. Byc moze nie-wprost to zly tok myslenia.

[Qń]

Wskazówka:
Droga Eulera w grafie istnieje wtedy i tylko wtedy gdy stopień wszystkich wierzchołków poza co najwyżej dwoma jest parzysty (a cykl Eulera wtedy i tylko wtedy, gdy stopień wszystkich wierzchołków jest parzysty. Dowód tego faktu w jedną stronę (w tę która Ci potrzebna) jest zresztą łatwy.

Q.

[filip.wroc]

ok... droga Eulera to droga prosta przez wszystkie krawedzie?

Jesli tak, to to juz spelnia wszystko czego potrzebuje, bo cwiczeniowiec dowod twierdzen na ktore sie powolujemy nie potrzebuje, wystarczy ze je przytoczymy w dowodzie zwiazanym z zadaniem

Czyli nie ma takiej drogi, poniewaz graf jest 3-regularny (wszystkie wierzcholki maja po 3 krawedzie wychodzace), a 3 jest nieparzyste.

Dzieki.