Расширением n-вершинного графа G называется граф H с n+1 вершинами такой, что граф G вкладывается в каждый максимальный подграф графа H. Тривиальное расширение графа G – соединение графа G с одноэлементным графом (т.е. к графу G добавляется вершина, которая соединяется ребром с каждой вершиной графа G). Т-неприводимым расширением графа G называется расширение графа G, получаемое из тривиального расширения данного графа удалением максимально возможного набора добавленных при построении тривиального расширения ребер.
