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

V принадлежащих одной компоненте связности Г . Пусть А, В - две вершины компоненты связности Гл графа Г , причем в \А,В} нет вершин Г . Тогда { А , в ] = ;.1 . Пусть fi буква из {А, В] , ноторая не сокращается в {А , В) . Тогда она сокра­ щается с некоторым однобуквенным подсловом Д у \ которое не принадлежит никакой вершине Гс, . Тогда / A 'A A s ^ * но ли<5° A •J либо В содержится в { А , Р) причем одновремен­ но оба они не могут содержаться в / А , А? • *^г0 противоречит связности r¿_ . Поэтому если некоторая вершина С компоненты Q графа Г содержится в { А, В) для вершин А ;В компоненты п V то и всякая вершина /J содержится в { А , в ] . Следовательно, множество компонент графа Г частично упорядочено отношением < *; если считать, что Гл < Гл для всякой ком­ поненты, а для /Z l ъ Гр таких, что Г ± Г р , Гр по определенно означает, что некоторая вершина Гл содержится в 71 между какими-то вершинами Г^ . % / Если бы в некоторой компоненте Гл было больше X вершин; являощихся Д - словами, то какая-то пара нх А ближайших друг к другу, лежала в одном ф - слове. Но { А , в J = $ i ■, что противоречит определению Д - слов. Из сказанного выша относительно порядка на множестве компонент графа обычными комбинаторными соображениями получаем, что число тех компонент графа, которые содержат в сего две вершины, и вершины никаких двух компонент не расположены в одной ж той же паре f - слов,1 не превышает %Х~3 . Используя это рассуждение; полу­ чаем, что число тех компонент, которые содержат по крайней мере тр * j вершины", либо содержат связанные вхождения;' не больше, чем *;