Доказательство. Пусть графG = (V, U) удовлетворяет условиям теоремы

Пусть граф G = (V, U) удовлетворяет условиям теоремы. Построим ядро графа G с помощью следующей процедуры.

1. Обозначим S ₁ базу графа G. Определим множество

V ₁ = S ₁ È G ^{- 1} (S ₁).

Удалим из G вершины V ₁ вместе с ведущими в них ребрами.

3. В полученном графе G ¹ найдем базу S ₂, для которой

S ₂ Г ^-1 (Г ^-1 (S ₁) \ V ₁) (1).

То есть в базе S ₂ содержатся только такие вершины G, из которых в вершины S ₁ ведут пути длины 2.

Такая база существует, поскольку в графе G из всякой вершины v Î V \ S ₁ ведет путь в некоторую вершину множества S _1. Тогда всякий такой путь из вершины, не являющейся соседней с вершинами множества S ₁, проходит через вершины, лежащие от вершин множества S ₁ на расстоянии 2. Поэтому в G ¹ существует база, удовлетворяющая условию (1). Она состоит из вершин, находящихся на расстоянии 2 от вершин множества S ₁.

Образуем множество V ₂ = V ₁ È S ₂ È Г ^{- 1} (S ₂).

3. Удалим из G ¹вершины S ₂ È Г ^{- 1} (S ₂) вместе с ведущими в них ребрами.

4. Если еще удалены не все вершины исходного графа, то повторим действия 2 и 3.

Описанный процесс продолжаем до тех пор, пока не будут удалены все вершины исходного графа.

В результате будет построено семейство множеств вершин:

S ₁,..., S_m.

Образуем множество S = .

Покажем, что S является ядром графа G.

1. Множество S является внешне устойчивым, поскольку всякая вершина графа G в процессе удаления вершин этого графа попадает либо в некоторое множество S_i либо во множество Г ^{- 1} (S_i). Поэтому, если v V\S, то i (v Г ^-1 (S_i)), т.е. из v ведет ребро в некоторую вершину множества S_i, а значит и в вершину S.

2. Множество S является внутренне устойчивым. Докажем это утверждение методом от противного. Предположим, что во множестве S содержатся две соседние вершины v ₁ и v ₂ графа G.

Положим для определенности, что v ₁ S_i и v ₂ S_j, причем i < j. Это означает, что ребро, соединяющее эти вершины, ведет из v ₁ в v ₂. Эта ситуация изображена на рис. 5.29:

S ₁ S _{2 ...} S_i... S_j...

v ₁ v ₂

v ₀

Рис. 5.29

По определению последовательности множеств S ₁,.., S_m из вершины v ₂ в некоторую вершину v ₀ S_i ведет путь четной длины. Обозначим такой путь как W.

Так как S_i - это база подграфа, полученного из графа G на одном из шагов работы описанной выше процедуры, и последовательность v ₁, W - это путь в этом же подграфе, то
v ₀ = v _1, поскольку в противном случае вершина v ₁ не может входить в базу S_i.

Поэтому путь v ₁, W образует цикл нечетной длины в графе G. Это противоречит условиям теоремы. Следовательно, множество S является внутренне устойчивым.