Un árbol de expansión o árbol recubridor de un grafo conexo "G" puede ser también definido como el mayor conjunto de aristas de "G" que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.