En este documento, proponemos un algoritmo de ramificación y poda para resolver exactamente el problema de la cobertura mínima de vértices (MVC). Dado que un límite inferior ajustado para MVC tiene una influencia significativa en la eficiencia de un algoritmo de ramificación y poda, definimos dos límites inferiores novedosos para ayudar a podar el espacio de búsqueda. Uno se basa en el grado de los vértices, y el otro se basa en el razonamiento de MaxSAT. El experimento confirma que nuestro algoritmo es más rápido que los algoritmos exactos anteriores y puede encontrar mejores resultados que los algoritmos heurísticos.