Формально, нехай G = (V, E) — будь-який граф, і нехай S ⊂ V — підмножина вершин графа G. Тоді породжений підграф G[S] — це граф, вершинами якого є елементи S а ребра якого складаються з усіх ребер з множини E кінцеві вершини яких належать S[1]. Одне і те ж визначення підходить для неорієнтованих графів, орієнтованих графів і навіть для мультиграфів.
Породжений підграф G[S] може бути також названий підграфом, породженим у G набором вершин S або (якщо контекст не призводить до двозначності) породженим підграфом вершин S
David S. Johnson. The NP-completeness column: an ongoing guide // Journal of Algorithms. — 1985. — Т. 6, вип. 3. — С. 434–451. — DOI:10.1016/0196-6774(85)90012-4.