spójność krawędziowa a stopień wierzchołka

[Karolina93]

W grafie G zachodzi nierówność:
\(\displaystyle{ \lambda \left( G\right) \le \delta \left( G\right)}\)

\(\displaystyle{ \lambda \left( G\right)}\)-spójność krawędziowa
\(\displaystyle{ \delta \left( G\right)}\)-minimalny stopień

Jak udowodnić taką nierówność ? Proszę o pomoc

[thom]

Rozważ wierzchołek o minimalnym stopniu \(\displaystyle{ \delta(G)}\) i usuń z grafu wszystkie krawędzie z niego wychodzące. Graf z pewnością stanie się niespójny, co więc to oznacza dla \(\displaystyle{ \lambda(G)}\)?

[Karolina93]

Jakoś tego nie widzę. Jeżeli usunę wszystkie krawędzie z wierzchołka, to ten wierzchołek będzie wierzchołkiem izolowanym. A co z tego wynika nie wiem ?

[thom]

Po usunięciu \(\displaystyle{ \delta(G)}\) krawędzi graf przestaje być spójny. A jak definiuje się liczbę \(\displaystyle{ \lambda(G)}\)?

[Karolina93]

Po usunięciu \(\displaystyle{ \delta(G)}\) krawędzi graf przestaje być spójny. A jak definiuje się liczbę \(\displaystyle{ \lambda(G)}\)?

Znam dwie definicję.
Najmniejsza liczba krawędzi, którą należy usnąć aby graf przestał być spójny.
Liczba krawędzi należących do najmniej licznego rozcięcia grafu.

Czyli , liczba krawędzi wynosi \(\displaystyle{ 0}\)w najmniej licznym rozcięciu , a stopień wierzchołka również \(\displaystyle{ 0}\) czyli nierówność jest spełniona ?

[thom]

Najmniejsza liczba krawędzi, którą należy usnąć aby graf przestał być spójny.

Zatem \(\displaystyle{ \lambda(G)\leq\delta(G)}\).

[Karolina93]

Najmniejsza liczba krawędzi, którą należy usnąć aby graf przestał być spójny.

Zatem \(\displaystyle{ \lambda(G)\leq\delta(G)}\).

No właśnie dlaczego zatem ? Z czego to wynika ? Nie mogę się połapać

[thom]

Wystarczy usunąć \(\displaystyle{ \delta(G)}\) krawędzi, aby graf nie był spójny, podczas gdy \(\displaystyle{ \lambda(G)}\) jest minimalną liczbą krawędzi potrzebną do uzyskania tego efektu.

[Karolina93]

I teraz jest jasne, dziękuje