Zadania z grafów, dyskretna

[Student_matmy]

Witam potrzebuje pomoc z następującymi zadaniami:

1. Pokazać, że jeśli G jest 3-regularnym grafem hamiltonowskim, to jego krawędzie można oznaczyć literami a, b, c w taki sposób, aby z każdego wierzchołka wychodziły krawędzie o różnych etykietach.

2. Pokazać, że graf Petersena nie jest grafem hamiltonowskim.

[Qń]

W pierwszym z Lematu o uściskach dłoni wynika, że graf musi mieć parzystą ilość wierzchołków, a zatem cykl ma parzystą długość. Oznaczamy więc krawędzie cyklu na przemian przez \(\displaystyle{ a}\) i \(\displaystyle{ b}\), a krawędzie spoza cyklu przez \(\displaystyle{ c}\). Wystarczy chwilę się zastanowić, żeby zobaczyć dlaczego to działa.

A dowód drugiego oparty na pierwszym zadaniu znajdziesz na przykład tu:
... 08-k25.pdf

Q.