Grafy

[welik]

Witam
Prosiłbym o pomoc w rozwiązaniu takich zadań z grafów

Udowodnić, że każdy graf prosty, który ma \(\displaystyle{ n}\) wierzchołków i więcej niż \(\displaystyle{ \frac{(n−1)(n−2)}{2} }\) krawędzi jest grafem spójnym.
Kompletnie nie wiem jak do tego podejść.

Zbadać, które z poniższych zdań jest prawdziwe.
a) Wszystkie grafy proste o 5 wierzchołkach i 9 krawędziach są izomorficzne.
mam kilka takich podpunktów, prosiłbym o przykładowe rozwiązanie a resztę zrobie sam

Zbadać, które z poniższych zdań dotyczących grafów prostych jest prawdziwe.
a) Niespójny graf bez cykli o 10 krawędziach ma więcej niż 11 wierzchołków.
Tu też prosiłbym o wskazówki do jednego, a reszte spróbuje sam

Z góry dzięki

[kerajs]

Udowodnić, że każdy graf prosty, który ma \(\displaystyle{ n}\) wierzchołków i więcej niż \(\displaystyle{ \frac{(n−1)(n−2)}{2} }\) krawędzi jest grafem spójnym.
1) jeden wierzchołek jest izolowany

Graf pełny o \(\displaystyle{ n-1 }\) wierzchołkach ma \(\displaystyle{ \frac{(n−1)(n−2)}{2} }\) krawędzi. Skoro krawędzi jest więcej to nie można odizolować jednego wierzchołka.
2) graf to dwa izolowane od siebie podgrafy o \(\displaystyle{ k}\) i \(\displaystyle{ n-k}\) wierzchołkach.
Tu policz ile krawędzi ma \(\displaystyle{ K_ k}\) i \(\displaystyle{ K_{n-k}}\)
3) 3 lub więcej izolowanych podgrafów
…..

a) Wszystkie grafy proste o 5 wierzchołkach i 9 krawędziach są izomorficzne.

Graf pełny o 5 wierzchołkach ma 10 krawędzi, więc przeetykietowanie takiego grafu pozbawionego jednej krawędzi jest zawsze możliwe.

a) Niespójny graf bez cykli o 10 krawędziach ma więcej niż 11 wierzchołków.

1. Graf niespójny zawiera co najmniej 2 izolowane podgrafy.
2. Jeśli graf spójny o k wierzchołkach nie zawiera cyklu to posiada on \(\displaystyle{ k-1}\) krawędzi.
3. Jeśli graf o k wierzchołkach nie zawiera cyklu to posiada on co najwyżej \(\displaystyle{ k-1}\) krawędzi.
Dzieląc graf na dwa (wzajemnie izolowane) spójne podgrafy o \(\displaystyle{ n}\) i \(\displaystyle{ 10-n}\) krawędziach potrzeba \(\displaystyle{ n+1}\) i \(\displaystyle{ 10-n+1}\) (razem 12) wierzchołków
Dzieląc graf na trzy (wzajemnie izolowane) spójne podgrafy o \(\displaystyle{ n}\), \(\displaystyle{ m}\) i \(\displaystyle{ 10-n-m}\)krawędziach potrzeba … .
itd