Изменения

О добавлении ребра в граф

|statement=

|proof=

''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место, то исходная последовательность будет мажорироваться полученной.

|statement=

Пусть:

* <tex> n = |VG| \geq 3 </tex> — количество вершин,

* <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex> — его последовательность степеней.

Тогда если <tex> \forall k \in \mathbb N </tex> верна импликация: <br>

<center><tex> d_k \leq k < n/2 \rightarrow d_{n - k} \geq n - k, (*) </tex></center>

|proof=

Для доказательства теоремы, докажем 3 леммы.

Будем считать, что <tex> \deg u \leq \deg v </tex>.

Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e </tex>.

Отбрасывая ребро <tex> e </tex>, получим гамильтонову <tex> (u, v) </tex>-цепь в графе <tex> G </tex>: <tex> u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = v </tex>.

Пусть <tex> S = \{ i | e_i = u_1 u_{i + 1} \in EG\}, T = \{ i |f_i = u_i u_n \in EG\} </tex>.

|statement=

|proof=

Пусть <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>: <tex> u_1 \rightarrow^{e_j} u_{j + 1} \rightarrow u_{j + 2} \rightarrow \ldots \rightarrow u_n \rightarrow^{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 </tex>, что противоречит условию, что граф негамильтонов. Значит, <tex> S \cap T </tex>, q.e.d.