  The software system under test can be modeled as a graph comprising of a set
of vertices, (V) and a set of edges, (E). Test Cases are Test Paths over the
graph meeting a particular test criterion. In this paper, we present a method
to achieve the minimum number of Test Paths needed to cover different
structural coverage criteria. Our method can accommodate Prime Path, Edge-Pair,
Simple & Complete Round Trip, Edge and Node coverage criteria. Our method
obtains the optimal solution by transforming the graph into a flow graph and
solving the minimum flow problem. We present an algorithm for the minimum flow
problem that matches the best known solution complexity of $O(|V| |E|)$. Our
method is evaluated through two sets of tests. In the first, we test against
graphs representing actual software. In the second test, we create random
graphs of varying complexity. In each test we measure the number of Test Paths,
the length of Test Paths, the lower bound on minimum number of Test Paths and
the execution time.

Software Engineering