En teoría de Grafos , una cobertura de aristas de un grafo es un conjunto de aristas donde cada vértice del grafo es incidente en al menos en una arista del conjunto.
Formalmente, una cobertura de aristas sobre el grafo G es un conjunto de aristas C donde cada vértice es incidente con al menos una arista en C. Se dice que el conjunto C cubre los vértices de G. La siguiente imagen muestra ejemplos de cobertura de aristas en dos grafos.
Una cobertura de aristas mínima es una cobertura de aristas del menor tamaño posible.
Notar que en la figura de la derecha no solo es una cobertura de aristas si no también un matching.
En particular, es un matching perfecto: un maching M en donde cada vértice es incidente con exactamente una arista en M. Un matching perfecto es siempre una cobertura de aristas mínima.