Cтраница 2
Квазилабиринт, у которого каждое приписанное ребру слово есть слово над В, назовем ЭД - квазилабиринтом. Очевидно, подобные слова р к. Если 21-квазилабиринт L получен из 9 ( - квазилабиринта LI заменой отметок ребер на подобные им отметки, то скажем, что L и L2 подобны. Очевидно, что поведения ЭД в L и в L2 одинаковы. [16]
Поэтому лемму достаточно доказать для ЭД-квазилабиринтов, у которых отметкой каждого ребра служит слово х В. Для одного ребра утверждение очевидно. Пусть оно доказано для всех деревьев, имеющих не более k ребер, и L - квазилабиринт, у которого дерево t ( L) имеет k ребро. Пусть v - висячая вершина дерева t ( L), в которую ведет ребро г из вершины и. В этой укладке к точке ф () не примыкает отрезок, ведущий в направлении, определенном отметкой ребра г, и можно получить укладку L, если присоединить к ф ( и) такой отрезок, имеющий достаточно малую длину. [17]