Ученые записки математических кафедр вып. 1970 г.

так к&к если в некоторой вершине содержится как подслово связанное вхождение1, т о , по определенно его , а также по определению /г - слова, получаем, что либо наша вершина сокращается в разных ф - словах, либо некоторое соседнее с ней подслово Yip сокращает­ ся не в том Ф - слове, в котором сокращается наша вершина. Чтобы доказать последнее утверждение леммы, заметим, что либо связанное слово А сокращается в разных ф - словах1; либо оно соседствует с таким вхождением СО в УС-Р ', что сокращается в Ф - слове, отличном от то го , где сокращается А . Следова­ тельно, используя упомянутое выше комбинаторное рассуждение1, полу­ чаем, что число связанных подслов 'Ylр не'больше 3■ (2 Х~3) а в данном ф - слове их не больше, чем 3 (X ~ 1) . Мы будем использовать также ннккй суграф СГ графа Г V который определяется так: множество вершин графов совпадает, а из множества ребер Г выбрасывайся такие ( V J . V l / , что V , м суть р - подслова Yip и не существует свободного подслова У> входящего в V] ж сокращажэщегося в . Будем полагать, что на множестве компонент СГ установлен частич­ ный порядок < ', как это сделано для Г в лемме I . ЛИКА 2. Число изолированных вершин графа СГ не больше1, чей Число таких компонент связности СГ которые содер­ жат не менее трех вервий, не превосходит Z X ~3 . В каждой ком­ поненте связности СГ не больше X веринн, являющихся р - словами. Доказательство последних двух утверждений следует из леммы I. Что касается первого утверждения, то легко видеть, что число изо­ лированных вершин СГ заведомо меньше числа всех вершин тех ком­ понент Г *; о которых говорится в утверждении 3 леммы I.