Sous-graphe d'un graphe
Un graphe G = (L, S) étant donné, un sous-graphe de G est un graphe G1 = (L1, S1) formé d'un sous-ensemble S1 de sommets de G et d'un sous-ensemble L1 d'arêtes de L.
Exemple
Soit le graphe G ci-dessous défini par G = (L, S), où L = {a, b, c, d, e, g, f, g, h, m, n} et S = {A, B, C, D, E, F}. Le graphe G1 = (L1, S1), tel que L1 = {a, b, g, n} et S1 = {A, B, C, E}, est un sous-graphe de G.