Droga Eulera w grafie niespójnym.

[colma]

Dzień dobry,

rozwiązuję następujące trzy zadania, jednak nie mam podanych odpowiedzi, więc prosiłbym o pomoc.

1) Warukiem koniecznym na to by niezorientowany graf \(\displaystyle{ G=\left\langle V,E\right\rangle }\) posiadał drogę Eulera jest by:
a) liczba jego krawędzi była co najmniej równa liczbie jego wierzchołków;
b) graf był spójny;
c) wszystkie jego wierzchołki miały stopień nieparzysty;
d) dla dowolnych dwóch wierzchołków istniała droga, która je łączy;

Ad. Zastanawiam się, czy oprócz odpowiedzi A również odpowiedzi B i D są prawidłowe. Rozumiem, że graf jest spójny, gdy istnieje droga między dowolnymi jego wierzchołkami. Jednak jeśli graf jest niespójny (tutaj wyobrażam to sobie jako dwa rozłączone grafy z \(\displaystyle{ 3}\) wierzchołkami rzędu drugiego i \(\displaystyle{ 3}\) krawędziami; tj. typowe trójkąty), to mogę wyznaczyć drogę Eulera na każdym z tych "podgrafów". Więc czy warunkiem koniecznym jest to, że graf jest spójny?

Wskaż zdania prawdziwe:
a) Jeśli graf ma drogę Hamiltona, to ma drogę Eulera.
b) Jeśli graf ma drogę Eulera, to ma drogę Hamiltona.
c) Jeśli graf \(\displaystyle{ G}\) ma drogę Eulera, to ma co najwyżej jeden wierzchołek stopnia nieparzystego.
d) Skończony graf spójny, niezorientowany, w którym każdy wierzchołek ma stopień parzysty, ma cykl Eulera.

Ad. tutaj zaznaczyłem A i D. Odpowiedź C jest nieprawdziwa, ponieważ potrzebne są min. dwa wierzchołki stopnia nieparzystego. Odpowiedź B również po rozrysowaniu dwóch przykładowych grafów wydaje mi się nieprawdziwa. Czy to prawda?

Niech \(\displaystyle{ G}\) będzie danym grafem prostym o \(\displaystyle{ n}\) wierzchołkach i \(\displaystyle{ m}\) krawędziach. Która z własności jest prawdziwa?
a) Jeśli \(\displaystyle{ G}\) jest grafem pełnym, to \(\displaystyle{ m=n\cdot n}\).
b) Jeśli \(\displaystyle{ n=m}\), to \(\displaystyle{ G}\) jest spójny.
c) Jeśli \(\displaystyle{ m > n}\), to graf \(\displaystyle{ G}\) ma cykl.
d) Jeśli \(\displaystyle{ m>n}\), to między dowolnymi dwoma wierzchołkami istnieje co najmniej jedna droga.

Ad. Zaznaczyłem B,C,D. (A) wydaje mi się nieprawdziwe, ponieważ graf pełny z definicji musi mieć bezpośrednią drogę między każdym wierzchołkiem. Jeśli narysuję typowy trójkąt (\(\displaystyle{ 3}\) wierzchołki, \(\displaystyle{ 3}\) krawędzie) to jest to graf pełny, ale \(\displaystyle{ 3 = 3\cdot 3}\). Czy to prawda?

Dziękuję za pomoc.