Подграфом графа называется граф, являющийся подмоделью исходного графа. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).
Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U.
Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.
Два последних определения дают два вида максимальности подграфов: максимальность множества рёбер и максимальность множества вершин.