Podgraf danego grafu G to graf powstały przez usunięcie z grafu G pewnej liczby wierzchołków lub krawędzi (z tym zastrzeżeniem, że usuwając pewien wierzchołek usuwamy wszystkie do niego przyległe krawędzie)^[1].

W szczególności każdy graf jest swoim podgrafem.

Podgrafem indukowanym wierzchołkowo danego grafu G nazywamy graf powstały przez usunięcie z grafu G pewnej liczby wierzchołków oraz wszystkich wychodzących z nich i wchodzących do nich krawędzi. Inaczej mówiąc jest to graf, którego zbiór wierzchołków jest zawarty (jest podzbiorem) w zbiorze wierzchołków grafu G, a zbiór krawędzi składa się ze wszystkich krawędzi grafu G, których końce należą do zbioru wierzchołków nowo powstałego grafu. Zbiór wierzchołków tego podgrafu nie może być pusty^[1].

Podgrafem indukowanym krawędziowo danego grafu G nazywamy graf powstały z grafu G, którego zbiór krawędzi jest zawarty (jest podzbiorem) w zbiorze krawędzi grafu G, a zbiór wierzchołków stanowią końce krawędzi.

• teoria grafów