El problema de encontrar una coincidencia acíclica máxima en un grafo no dirigido simple se sabe que es NP-completo. En este documento, presentamos nuevos resultados; mostramos que una coincidencia acíclica máxima en un grafo no dirigido dado (con vértices y aristas) se puede calcular de forma recursiva con una profundidad de recursión en expectativa. En consecuencia, empleando un cálculo recursivo de una coincidencia acíclica máxima en un grafo dado, si la profundidad de recursión cumple con la expectativa, entonces se puede calcular una coincidencia acíclica máxima en tiempo y espacio . Sin embargo, para el caso general, la complejidad del cálculo recursivo de una coincidencia acíclica máxima es en tiempo y en espacio.