O tamanho do grafo G é dado por |V| + |E|. Um subgrafo H = (V ,E ) de um grafo G = (V,E) é um grafo tal que V ⊆ V, E ⊆ E. Um subgrafo gerador de G é um subgrafo H com V = V. O grau (degree) de um vértice v, denotado por d(v) é o número de arestas incidentes a v, com laços contados duas vezes.