Изменения

<center><tex> d_k \leqslant k < n/2 \rightarrow Rightarrow d_{n - k} \geqslant n - k, (*) </tex></center>

<tex> d_k \leqslant k \Leftrightarrow |\{ v \in VG | \mid d_v \leqslant k \}| \geqslant k. </tex>

"<tex> \Rightarrow </tex>" Пусть:

<tex> \{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG | \mid d_v \leqslant k \} \Rightarrow |\{ v \in VG | \mid d_v \leqslant k \}| \geqslant k </tex>.

"<tex> \Leftarrow </tex>" ПустьИз условия:* <tex> |\{ v \in VG | \mid d_v \leqslant k \}| = k + p </tex>,

<tex>\ d_{n - k} \geqslant n - k \Leftrightarrow |\{ v \in VG | \mid d_v \geqslant n - k \}| \geqslant k + 1. </tex>

"<tex> \Rightarrow </tex>" Пусть:

<tex> \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subseteq \{ v \in VG | \mid d_v \geqslant n - k \} \Rightarrow \{ v \in VG | \mid d_v \geqslant n - k \} \geqslant k + 1 </tex>.

"<tex> \Leftarrow </tex>" Пусть:* <tex> |\{ v \in VG | \mid d_v \geqslant n - k \}| = k + 1 + p, (p \geqslant 0)</tex>,

# Пусть Если <tex> d'_k > k </tex>. Тогда , то первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.# Пусть Если <tex> d'_k \leqslant k, \mbox{ } d'_{n - k} \geqslant d_{n - k} \geqslant n - k </tex>. Тогда , то оба аргумента импликации всегда истинны. Значит, и в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.

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

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