Matematyka.pl

Witam
Mam problem z trzema zadaniami:

1. Czy graf regularny stopnia \(\displaystyle{ r}\) mający \(\displaystyle{ 2r + 1}\) wierzchołków musi być eulerowski?

2. Dla jakich \(\displaystyle{ n}\) graf pełny \(\displaystyle{ K_n}\) można przedstawić w postaci dwóch dopełniających się grafów
częściowych eulerowskich?

3. W grafie spójnym \(\displaystyle{ G, 2k}\) wierzchołków ma stopień nieparzysty, a pozostałe wierzchołki są stopnia parzystego. Pokaż, że w \(\displaystyle{ G}\) istnieje \(\displaystyle{ k}\) krawędziowo rozłącznych dróg, które pokrywają wszystkie krawędzie \(\displaystyle{ G}\). (Rozkład grafu na tzw. drogi jednobieżne.)

Czy byłby w stanie ktoś mi pomóc z ich rozwiązaniem i wytłumaczeniem dlaczego tak jest?
z góry dzięki

1) \(\displaystyle{ 2|E(G)| =r(2r+1)}\) skąd \(\displaystyle{ r}\) musi być parzyste a więc \(\displaystyle{ G}\) jest grafem eulerowskim.

2) W grafie, w którym istnieje cykl Eulera każdy wierzchołek ma parzysty stopień i jest to graf spójny. Dla \(\displaystyle{ n}\) parzystego każdy wierzchołek ma stopień nieparzysty, wiec w pewnym z podgrafów ten wierzchołek musiałby występować w stopniu nieparzystym - sprzeczność.
Dla \(\displaystyle{ n = 3}\) widać, że się nie da.
Dla nieparzystego \(\displaystyle{ n \ge 5}\) bierzemy następujący podział: cykl Hamiltona tej kliki (kolejno wierzchołki 1, 2, 3, ..., n, 1 połączone krawędziami) i graf złożony z pozostałych krawędzi. Cykl Hamiltona ma wierzchołki parzystego stopnia, więc ten drugi graf też ma. Ten drugi graf jest spójny, bo ma drzewo rozpinające złożone ze wszystkich wierzchołków kliki - wierzchołek \(\displaystyle{ 1}\) jest połączony ze wszystkimi pozostałymi poza \(\displaystyle{ 2}\) i \(\displaystyle{ n}\), ale \(\displaystyle{ 2}\) jest połączone z \(\displaystyle{ n}\) i \(\displaystyle{ n - 1}\) z \(\displaystyle{ 2}\).
Odpowiedź: nieparzyste \(\displaystyle{ n \ge 5}\).

3) Łączymy krawędziami specjalnymi pary wierzchołków nieparzystego stopnia. W tak utworzonym grafie każdy wierzchołek ma stopień parzysty, czyli jest cykl Eulera. Bierzemy ten cykl i usuwamy z niego te \(\displaystyle{ k}\) krawędzi specjalnych. Dwie krawędzie specjalne nie mogą na tym cyklu być kolejnymi krawędziami, bo nie mają wspólnych wierzchołków. Po usunięciu krawędzi cykl rozpada się na \(\displaystyle{ k}\) krawędziowo rozłącznych ścieżek, cnd.