Zadania z matematyki dyskretnej do sprawdzenia #2

[gardner]

2.2. G jest grafem o p wierzchołkach. Jeśli stopień najmniejszego wierzchołka
jest \(\displaystyle{ \ge \frac{p-1}{2}}\)to \(\displaystyle{ G}\) jest spójne.
Wskazówka?
2.4. Dla każdych \(\displaystyle{ G}\) i \(\displaystyle{ k}\), jeśli najmniejszy stopień wierzchołka wynosi \(\displaystyle{ k}\) to \(\displaystyle{ G}\) zawiera \(\displaystyle{ k}\)-regularny podgraf.
Oczywiste,gdy stopień każdego wierzchołka wynosi \(\displaystyle{ k}\)-każdy podgraf jest swoim podgrafem. Ale co w innym przypadku?
2.5. Graf \(\displaystyle{ G}\) lub jego dopełnienie jest spójny.
Oczywiste,bo dopełnieniem grafu niespójnego jest graf spójny. Wskazane jest przeprowadzać jakiś bardziej skomplikowany dowód?
2.6. Jeśli \(\displaystyle{ G}\) jest izomorficzny z \(\displaystyle{ G}\) i nietrywialny to \(\displaystyle{ 2 \le diam(G) \le 3}\)
Wydaje się dość trudne,było z gwiazdką
2.7. Dla jakich \(\displaystyle{ k}\) i \(\displaystyle{ p}\) istnieje \(\displaystyle{ k}\)-regularny graf o \(\displaystyle{ p}\) wierzchołkach?
\(\displaystyle{ \sum_{}^{} deg(v)=2\left| E\right|}\)
\(\displaystyle{ pk=2\left| E\right|}\)
\(\displaystyle{ \left| E\right| = \frac{pk}{2}}\)
\(\displaystyle{ 2/p \vee 2/k}\) O to chodziło?
2.9. Jeśli \(\displaystyle{ G}\) jest \(\displaystyle{ 4}\)-regularny to krawędzie grafu \(\displaystyle{ G}\) można pomalować na czerwono i zielono tak,że w każdym wierzchołku spotykają się dwie krawędzie czerwone i dwie zielone.
Hmm tutaj można przeprowadzić takie rozumowanie,że na pewno istnieje cykl Eulera(zakładam że spójny,parzystość wierzchołków spełniona)-maluję ten cykl na jeden kolor. Pozostaje kolejny cykl Eulera i robię z nim to samo.
2.10. Zbiór krawędzi dowolnego cyklu jest sumą parami rozłącznych zbiorów krawędzi cykli
prostych
Tutaj podobne rozumowanie co w 2.9?

Czekam na odpowiedzi i czekam również na te z poprzedniego posta.

[wiedzmac]

Oczywiste,bo dopełnieniem grafu niespójnego jest graf spójny. Wskazane jest przeprowadzać jakiś bardziej skomplikowany dowód?

To raczej nie jest dowód. Należy przeprowadzić dowód, chodź nie jest on specjalnie skomplikowany.
Ogólnie widzę że pełno zadań potraktowałeś jako oczywiste, a chyba nie o to chodzi.

[Medea 2]

Zadanie 2.6 jest bez sensu, bo z tego co jest mi wiadome, każdy graf jest izomorficzny ze sobą.

[gardner]

Oczywiste,bo dopełnieniem grafu niespójnego jest graf spójny. Wskazane jest przeprowadzać jakiś bardziej skomplikowany dowód?

To raczej nie jest dowód. Należy przeprowadzić dowód, chodź nie jest on specjalnie skomplikowany.
Ogólnie widzę że pełno zadań potraktowałeś jako oczywiste, a chyba nie o to chodzi.

Właśnie dlatego się zapytałem - w niektórych przypadkach pewnie można użyć takiego sformułowania-jeżeli go użyłem to pewnie nie miałem pomysłu na lepsze wyjaśnienie.
Może wiesz jak zrobić to porządnie?

Zadanie 2.6 jest bez sensu, bo z tego co jest mi wiadome, każdy graf jest izomorficzny ze sobą.

Tak,zgadza się. Miałem błąd w treści. Tam chodziło o dopełnienie tego grafu.

[wiedzmac]

Właśnie dlatego się zapytałem - w niektórych przypadkach pewnie można użyć takiego sformułowania-jeżeli go użyłem to pewnie nie miałem pomysłu na lepsze wyjaśnienie.
Może wiesz jak zrobić to porządnie?

Oczywiście że można powiedzieć że jest to oczywiste, ale pewnie nie na tym poziomie wiedzy/edukacji.
A jak to zrobić porządnie?

Ukryta treść:    

Weźmy dowolny graf \(\displaystyle{ G}\).
Jeżeli jest on spójny to skończyliśmy zadanie. Załóżmy więc, że nie jest on spójny.

Skoro nie jest on spójny, to jest podzielony na co najmniej dwa kawałki (spójne składowe).
Popatrzmy na jego dopełnienie.
Weźmy teraz dowolne wierzchołki \(\displaystyle{ x, y}\) i pokażmy, że z jednego można dojść do drugiego (co implikuje że graf będzie spójny).

Jeżeli te dwa wierzchołki nie są w tej samej spójnej składowej to istnieje pomiędzy nimi krawędź (bo nie istniała w wyjściowym grafie).

Jeżeli są w tej samej spójnej składowej, to weźmy jakiś wierzchołek \(\displaystyle{ z}\) z innej spójnej składowej. Wtedy mamy krawędź między \(\displaystyle{ x}\) i \(\displaystyle{ z}\) oraz \(\displaystyle{ y}\) i \(\displaystyle{ z}\). Wtedy możemy sobie przejść z \(\displaystyle{ x}\) do \(\displaystyle{ z}\) a z \(\displaystyle{ z}\) do \(\displaystyle{ y}\). Czyli istnieje droga z \(\displaystyle{ x}\) do \(\displaystyle{ y}\). Z powyższych faktów wnioskujemy, że dopełnienie grafu \(\displaystyle{ G}\) jest spójne.