Теорема 4.1.1.

  такие, что

Доказательство:

y AE_i BE  G(A,B) = C(p_AB|y_i)

Рассмотрим путь T={S,A₁,A₂,..,A_n,p^j} из начальной вершины S в класс p^j. Сила этого пути определяется как min весов дуг:

Причем, свойство 2.b граф-схемы гарантирует, что lk i_li_k. Следовательно:

C_G(T) = C(|)  , где

 = 

 =   

Малая буква p обозначает, как и ранее, цилиндрическое продолжение на все множество =[0,1]^D.

Ранее было показано, что y

где T - путь из S в p^j. Следовательно:

Обозначим:

Аналогичным образом строится доказательство для - дополнения граф-схемы необходимостей. Т.е.

.

Обозначим:

.

q.e.d.