Sea G = (V, E) un grafo (dirigido o no), un subgrafo del mismo es un grafo;
\(G_1\ =\ \left(V_1,\ E_1\right)\ donde:\ \varnothing\ne V_1\ \subseteq\ V\ y\ E_1\ \subseteq\ E\) y cada arista de \(E_1\) es incidente con los vertices de V.
Subgrafo Recubridor
Sea G = (V, E) un grafo (dirigido o no), un subgrafo recubridor es un grafo,
\(G_1\ =\ \left(V_{1,\ }E_1\right)\ donde\ V_1\ =\ V\ y\ E_1\subseteq\ E.\) Es decir mantenemos los vértices y modificamos eventualmente las aristas.
La cantidad de subgrafos recubridores de un grafo finito es \(2^n\).
Subgrafo Inductivo:
Sea G = ( V , E ) un grafo(dirigido o no) , sea U tal que, \(\varnothing\ne\) U\(\subseteq\) V , el subgrafo
de G inducido por U , es el subgrafo cuyo conjunto de vértices es U y que contiene
todas las aristas de G de la forma ( x , y ) ( { x , y } ), con x e y en U si G es
dirigido( no dirigido).
Grafo Completo:
Sea V no vacío un conjunto de vértices , el grafo completo sobre V , es un grafo
no dirigido , sin lazos , de forma que para todo a ,b \(\in\) V ,con a \(\ne\) b , entonces la
arista { a , b } , está en dicho grafo