1. Jeżeli w grafie \(\displaystyle{ G}\) istnieje cykl Eulera, to w grafie krawędziowym \(\displaystyle{ L \left( G \right)}\) także istnieje cykl Eulera.
2. Jeżeli w grafie krawędziowym \(\displaystyle{ L \left( G \right)}\) istnieje cykl Eulera, to w grafie \(\displaystyle{ G}\) także istnieje cykl Eulera.
Oto mój sposób na rozwiązanie tego zadania
Graf pełny \(\displaystyle{ n}\)-wierzchołkach posiada \(\displaystyle{ {n\choose k}}\) krawędzi.Krawędzie te staną się w grafie krawędziowym wierzchołkami.Policzymy stopnie tych wierzchołków.Weźmy dowolną krawędź grafy pełnego.Każdy wierzchołek ma stopień \(\displaystyle{ n-1}\).Pomijając krawędź \(\displaystyle{ e}\) jest to \(\displaystyle{ \left( n-2 \right)}\) krawędź \(\displaystyle{ e}\) łączy dwa wierzchołki w grafie pełnym ,więc w grafie krawędziowym jego wierzchołek będzie stopnia \(\displaystyle{ 2 \cdot \left( n-2 \right)}\).Co daje nam zawsze liczbę parzystą a jest to warunek który daje nam cykl Eulera w grafie nieskierowanym.
Kod: Zaznacz cały
http://wstaw.org/w/2bIs/Proszę o opinie.I o pomoc w rozwiązania przykładu drugiego.
