Teoria grafów.

[be-girl222]

Mam do udowodnienia, że jeśli graf jest spójny i ilość krawędzi jest równa ilości wierzchołków to istnieje dokładnie jeden cykl w grafie.

Bardzo proszę o sprawdzenie.


Wiem że \(\displaystyle{ \sum_{v \in V} deg(v)= 2|E|}\), gdzie E jest zbiorem krawędzi, V jest zbiorem wierzchołków. Z założenia wynika że \(\displaystyle{ \sum_{v \in V} deg(v)= 2|V|}\) (warunek 1).
Skoro graf spójny to \(\displaystyle{ deg(v) \ge 1}\) dla każdego v.
Załóżmy, że |E|=|V|=n.


Więc najpierw udowodnię, że musi istnieć przynajmniej jeden cykl.

Załózmy że nie istnieje żaden cykl \(\displaystyle{ \Rightarrow}\) nie może istnieć ścieżka zamknięta \(\displaystyle{ \Rightarrow}\) nie może istnieć 2n krawędzi, ponieważ wtedy średnio na jeden wierzchołek przypadają 2 krawędzie, co prowadzi do powstania cyklu.


Teraz udowodnimy , że nie ma więcej cykli.
By istniało więcej niż jeden cykl to suma stopni wierzchołków musiałaby być większa niż 2|V|.

Będę wdzięczna za jakiekolwiek uwagi , ponieważ wiem że wykonany przez mnie dowód jest zbyt mało formalny.

[Inkwizytor]

Jeśli chodzi o więcej niż jeden cykl to można tak:

Załóżmy że są co najmniej 2 cykle. Jeśli wyrzuciłbym jedną krawędź należącą do jednego z cykli to nadal miałbym przynajmniej jeden cykl, \(\displaystyle{ n}\) wierzchołków i \(\displaystyle{ n-1}\) krawędzi. Ale tylko drzewa mają \(\displaystyle{ n}\) wierzchołków i \(\displaystyle{ n-1}\) krawędzi. Tak więc sprzeczność


To samo tylko w druga stronę wykorzystaj do udowodnienia istnienia jednego cyklu.