Development of cells with minimal functionality, containing only desired catalytic properties for chemical conversion and replication, are gaining importance since such minimal cells are expected to be the most efficient machinery for production of specific chemicals. In this paper, we propose a graph theory augmented recursive MILP approach to identify multiple minimal reaction sets in metabolic networks that are capable of satisfying predefined objectives (such as growth). The proposed approach uses graph theoretic insights to reduce computational time and a recursive MILP approach to identify multiple minimal reaction sets. Identifying such multiple minimal reaction sets facilitates development of best minimal cell based on other process requirements. The proposed approach is illustrated by identifying multiple minimal reaction sets that can produce predefined biomass in E.coli. © 2011 Elsevier B.V.