Paper III

We study the problem of minimal triangulation of graphs. One of the rst algorithms to solve this problem was Lex M, which was presented in 1976. A new algorithm, and a simplication of Lex M called MCS-M, was presented in 2002. In this paper we compare these two algorithms and show that they produce the same set of triangulations, answering an open question mentioned by the authors of MCS-M.