Помеченный граф– граф, у которого каждой вершине поставлена в соответствие некоторая уникальная отметка (символ, цифра), иначе – абстрактный.
Дополнение графа G –граф 
,такой, что 
,а 
(вершины смежные в 
несмежны в Gи наоборот).
Подграф 
графа 
–граф, у которого все вершины и ребра удовлетворяют следующим соотношениям 
.
Остовный подграф графа G -подграф, содержащийвсе вершины графа G, множество ребер есть подмножество ребер графаG.
Порожденный подграф (порожденный подмножеством вершин 
) – подграф, множество вершин которого 
,а множество ребер 
содержит все ребра графа G, инцидентные выбранным вершинам .
Например:
