I. Introduction
Due to the growing efficiency of SAT and MaxSAT solvers, the interest on solving NP-Complete and some NP-Hard problems with SAT or MaxSAT has grown. Among these problems, the ones related to graphs, like the Hamiltonian Cycle, Steiner Tree, Isomorphism and others problems, are widely studied.