Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
Формально, пусть G = (V, E) — любой граф, и пусть S ⊂ V — подмножество вершин графа G. Тогда порождённый подграф G[S] — это граф, вершинами которого являются элементы S, а рёбра которого состоят из всех рёбер из множества E, конечные вершины которых принадлежат S[1]. Одно и то же определение подходит для неориентированных графов, ориентированных графов и даже для мультиграфов.
Порождённый подграф G[S] может быть также назван подграфом, порождённым в G набором вершин S или (если контекст не приводит к двусмысленности) порождённым подграфом вершин S.
Задача изоморфизма порождённых подграфов является видом задачи поиска изоморфного подграфа, в которой целью является проверка, может ли один граф быть найден как порождённый подграф другого графа. Поскольку эта задача включает задачу о клике как частный случай, она NP-полна[4].