Bioprocesses are of growing importance as an avenue to produce chemicals. Microorganisms containing only desired catalytic and replication capabilities in their metabolic pathways are expected to offer efficient processes for chemical production. Realizing such minimal cells is the holy grail of metabolic engineering. In this paper, we propose a new method that combines graph-theoretic approaches with mixed-integer liner programming (MILP) to design metabolic networks with minimal reactions. Existing MILP based computational approaches are computationally complex especially for large networks. The proposed graph-theoretic approach offers an efficient divide-and-conquer strategy using the MILP formulation on sub-networks rather than considering the whole network monolithically. In addition to the resulting improvement in computational complexity, the proposed method also aids in identifying the key reactions to be knocked-out in order to achieve the minimal cell. The efficacy of the proposed approach is demonstrated using three case studies from two organisms, Escherichia coli and Saccharomyces cerevisiae. (C) 2011 Elsevier Ltd. All rights reserved.