Another property of graphs has deep implications for testing: cyclomatic complexity.
The cyclomatic number of a graph G is given by V(G) = e – n + p. where
e is the number of edges in G n is the number of nodes in G p is the number of components in G
V(G) is the number of distinct regions in a graph. Recall our discussion of vector spaces and the notion of a basis set. One formulation of structural testing postulates the notion of basis paths in a program and shows that the cyclomatic number of the program is the number of these basis elements.
The cyclomatic number of our example graph is V(G) = 5 – 7 + 2 = 0. When we use cyclomatic complexity in testing. We will (usually) have strongly connected graphs, which will generate graphs with large cyclomatic complexity.