Subgrafos: Un grafo H es subgrafo de G si todos los vértices y todas las aristas de H están también presentes en G. Si además, el subgrafo H tiene el mismo número de vértices que G, decimos que es un subgrafo generador.
Cualquier grafo tiene un subgrafo generador simple. Si este subgrafo tiene el mayor número de aristas se llama grafo simple subyacente.
Grado de un vértice: Siendo G=(V,A) un grafo no dirigido, y v pertenece a V, el grado de v, dG(v), es el número de aristas incidentes con él. El conjunto de vértices adyacentes con v se denomina Γ(v).
En un grafo dirigido se diferencian el grado dalida ds(v) y el grado de entrada de(v). El grado total del vñertice es la suma de ambos, d(v)=de(v)+ds(v). En este caso, Γ(v) contiene los vértices que son extremo final de los arcos que salen de v, y Γ-1(v) a los vértices que son extremo inicial de los arcos que entran en v.
TEOREMA: El número de vértices de grado impar en un grafo, es par.