Es la asignación de etiquetas, tradicionalmente representada mediante enteros, alas aristas o vértices, o ambos, de un grafo.

Formalmente, dado un grafo G, un vértice etiquetado es una función que corresponde a vértices de G aun conjunto de etiquetas. Un grafo con tal función definida es llamado grafo de vértices etiquetados. De la misma manera, una arista etiquetada es una función de asignación de aristas de G tal conjunto de etiquetas. En este caso, G es llamado como grafo de aristas etiquetadas. Cuando las etiquetas de las aristas pertenecen a un conjunto ordenado(p.e. los números reales), esta puede ser llamado como grafo ponderado.

Es una tétrada {V, E, L, I}, donde:

· * V es un conjunto cuyos elementos son llamados vértices.

· *E c {e| e c V, |e| = 2} es un conjunto cuyos elementos son llamados aristas( cada arista es un conjunto de vértices con cardinalidad dos).

· *L es el conjunto de etiquetas