Разница между остовным и порождённым подграфом в теории графов заключается в следующем:

1. Остовный подграф имеет то же самое множество вершин, что и исходный граф, но множество дуг подграфа является подмножеством множества дуг исходного графа. 1
2. Порождённый подграф состоит из подмножества вершин множества вершин исходного графа и всех таких дуг графа, у которого конечные и начальные вершины принадлежат подмножеству. 1 Другими словами, порождённый подграф содержит все возможные (для своего множества вершин) рёбра графа. 3

Таким образом, остовный подграф содержит все вершины исходного графа, а порождённый — все возможные рёбра для определённого подмножества вершин. 34