Matematyka.pl

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

Proszę o pomoc w dowodzie tej nierówności.

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

Drugą nierówność łatwo uzasadnić w ten sposób, że dowolny graf można rozspójnić usuwając wszystkie krawędzie wychodzące z dowolnego wierzchołka. Więc jeśli weźmiemy wierzchołek o najmniejszym stopniu i usuniemy z niego wszystkie krawędzie to graf będzie niespójny. Możliwe, że da się zrobić to lepiej, czyli usuwając mniej krawędzi.

Podbijam gdyż też poszukuje dowodu

Pierwsza nierówność jest również oczywista,gdyż usuwając wierzchołek usuwamy również wchodzące i wychodzące z niego krawędzie. Tzn. usuwając dowolną krawędź na pewno można ją usunąć poprzez usunięcie wierzchołka z którym jest połączona (zawsze zabieramy co najmniej jedną krawędź - a dokładnie tyle ile wynosi \(\displaystyle{ deg v}\) gdzie \(\displaystyle{ v}\) to nasz wierzchołek) Oczywiste jest więc,że spójność wierzchołkowa jest mniejsza od krawędziowej (zawsze można rozspójnić graf "szybciej" usuwając wierzchołek niż krawędź)

Dowód lewej nierówności wcale nie jest taki łatwy. Jeśli nikt tego nie zrobi, napiszę go po pracy.

dzięki wielkie!

Twierdzenie 4.6 i jego dowód. Nie sprawdzałem dokładnie, czy dowód jest w 100% poprawny, ale na pewno trzeba zastosować indukcję.