Вершина, свързаност на ръба, връзка между тях и минималната степен на върха

Нека минималната степен на върха на графиката [math] G [/ math] се обозначава с буквата [math] \ delta [/ math]. Тогава:

1. Нека проверим второто неравенство. Ако графиката [math] G [/ math] няма ръбове, тогава [math] \ lambda = 0 [/ math]. Ако има ребра, тогава получаваме несвързана графика от дадената, премахвайки всички ребра, падащи на върха с най-малка степен. Както и да е [math] \ lambda \ leqslant \ delta [/ math] .
2. За да проверим първото неравенство, трябва да разгледаме няколко случая.
   1. Ако [math] G [/ math] е несвързана или тривиална графика, тогава [math] \ kappa = \ lambda = 0 [/ math] .
   2. Ако [math] G [/ math] е свързан и има мост [math] x [/ math], тогава [math] \ lambda = 1 [/ math]. В последния случай, [math] \ kappa = 1 [/ math], защото или графиката [math] G [/ math] има съвместна точка, падаща на ръба [math] x [/ math], или [math] G = K_2 [/ математика] .
   3. И накрая, да предположим, че графиката [math] G [/ math] съдържа набор от ръбове [math] \ lambda \ geqslant 2 [/ math], премахването на което я прави прекъсната. Ясно е, че изтривайки [math] \ lambda - 1 [/ math] ръбове от този набор, получаваме графика с мост [math] x = uv [/ math]. За всеки от тези [math] \ lambda - 1 [/ math] ръбове изберете всеки връх, инцидентен с него, различен от [math] u [/ math] и [math] v [/ math]. Премахването на избраните върхове премахва [math] \ lambda - 1 [/ math] (и вероятно повече) ръбове. Ако получената след такова изтриване графика не е свързана, тогава [math] \ kappa \ lt \ lambda [/ math]; ако е свързан, тогава има мост [math] x [/ math] и следователно премахването на върха [math] u [/ math] или [math] v [/ math] води или до несвързана, или до тривиална графика . Както и да е [math] \ kappa \ leqslant \ lambda [/ math] .

Да разгледаме графиката [math] G [/ math], която представлява обединението на две пълни графики [math] G_1 [/ math] и [math] G_2 [/ math], съдържащи върха [math] c + 1 [/ math] . Забележете [math] b [/ math] върхове, принадлежащи на подграф [math] G_1 [/ math] и [math] a [/ math] върхове, принадлежащи на подграф [math] G_2 [/ math]. Добавете ръбове към графиката [math] G [/ math] [math] b [/ math], така че всеки ръб да бъде случайно маркиран с връх, лежащ в подграф [math] G_1 [/ math] и маркиран връх, лежащ в подграф [math] G_2 [/ math] и няма нито един маркиран връх, който да няма поне един нов инцидент на ръба. Тогава:

---