Which one of the following statements is incorrect?
2012
Which one of the following statements is incorrect?
Answer: B. Cyclomatic complexity for a flow graph G is V(G) = N - E + 2, where E is the number of edges and N is the number of nodes in the flow graph. — ConceptMcCabe's cyclomatic complexity V(G) measures the number of linearly independent paths through a program's flow graph - the size of a basis set of…
- A.
The number of regions corresponds to the cyclomatic complexity.
- B.
Cyclomatic complexity for a flow graph G is V(G) = N - E + 2, where E is the number of edges and N is the number of nodes in the flow graph.
- C.
Cyclomatic complexity for a flow graph G is V(G) = E - N + 2, where E is the number of edges and N is the number of nodes in the flow graph.
- D.
Cyclomatic complexity for a flow graph G is V(G) = P + 1, where P is the number of predicate nodes contained in the flow graph G.
Attempted by 33 students.
Show answer & explanation
Correct answer: B
Concept
McCabe's cyclomatic complexity V(G) measures the number of linearly independent paths through a program's flow graph - the size of a basis set of paths, which is the number of test cases that basis-path testing requires and an upper bound on the number needed for full branch coverage. For a flow graph drawn from a single connected program, three standard formulations all yield the same value:
Graph-theoretic form: V(G) = E - N + 2C, where E is the number of edges, N is the number of nodes and C is the number of connected components; for a single component this reduces to V(G) = E - N + 2.
Region form: V(G) equals the number of regions into which a planar drawing of the flow graph divides the plane, counting the unbounded region outside the drawing.
Predicate form: V(G) = P + 1, where P is the number of predicate (decision) nodes in the flow graph.
Application
The stem asks which statement fails to match those definitions. The region statement, the E - N + 2 statement and the P + 1 statement each restate one of the three standard formulations exactly. The remaining statement, V(G) = N - E + 2, reverses the operands of the subtraction: the graph-theoretic form subtracts the node count from the edge count, never the edge count from the node count. That statement is the incorrect one.
Cross-check
Take the flow graph of two consecutive if-then-else constructs: an entry node that is also the first decision, its two branch nodes, a merge node that is also the second decision, its two branch nodes, and an exit node. That flow graph has N = 7 nodes, E = 8 edges and 2 predicate nodes.
Formulation | Value for this flow graph |
|---|---|
E - N + 2 (graph-theoretic form) | 8 - 7 + 2 = 3 |
Region count | 2 enclosed regions + 1 unbounded outer region = 3 |
P + 1 (predicate form) | 2 + 1 = 3 |
N - E + 2 (reversed subtraction) | 7 - 8 + 2 = 1 |
The disagreement is systematic rather than accidental. In a flow graph whose decision nodes are binary, every predicate node replaces one outgoing edge by two, so the counts are tied together as E = N - 1 + P. Substituting that relation gives E - N + 2 = P + 1, which is exactly the predicate form, while the reversed subtraction gives N - E + 2 = 3 - P. The two expressions agree only in the single case P = 1; for every other program the reversed form falls as more decisions are added, whereas the number of independent paths rises. This is why V(G) = N - E + 2 is the incorrect statement, and why the other three statements are the accepted equivalent definitions of cyclomatic complexity.