Подграфы

Граф называется подграфом графа , если , . Всякий подграф может быть получен из графа удалением некоторых вершин и ребер (при удалении вершины удаляются и все инцидентные ей ребра).

Подграф графа называется остовным, если . Остовный подграф получается удалением из графа некоторых ребер, вершины же остаются в неприкосновенности.

Порожденный подграф получается из графа удалением некоторых вершин. Все ребра, которые были в графе между оставшимися вершинами, должны сохраниться в подграфе. Говорят, что подграф порождается оставшимися вершинами.