Abstract: An optimization method based-on graph theory and mathematical programming for choosing the SoC FSM verification path is presented in this article. We analyze and solve the problems in FSM verification, and we also use this approach to reconstruct the verification steps of some IP modules' Golden Files of C*Core. In comparison with the original simulation results of C*Core, this approach shows its high efficiency by solving FSM verification problem in shorter time.