Граф каркасов

Граф каркасов (Tree graph) — граф $\mathcal {G}(G)$, вершины которого суть каркасы графа $G$ и две вершины смежны, если соответствующие каркасы имеют в точности $(n-2)$ общих ребер, где $n = |V(G)|$. Граф каркасов любого графа гамильтонов.

Литература

• Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.