Question

A delivery driver must travel from Source (S) to Destination (D).
Possible paths:
S → A → C → D,
S → B → C → D,
S → A → E → D,
S → B → F → D.
Rules:
1. A route cannot repeat a node.
2. A route cannot have more than 3 edges.
3. C cannot be visited if E is visited.
4. B cannot be used if F is used.
How many valid routes exist from S to D?

• A. 3
• B. 4
• C. 5
• D. 6

Hint:

When validating routes, check dependency constraints like “cannot use X if Y is used” independently for each path.

Answer 1

The Correct Option is A

We examine each listed route and apply the rules:
1. S → A → C → D
No repeated nodes, exactly 3 edges, and does not use E or F. Valid.
2. S → B → C → D
No repeated nodes, exactly 3 edges, uses B and C, does not use E or F. Valid.
3. S → A → E → D
Contains E. By Rule 3, if E is visited, C cannot be used.
This route does not use C, so it is valid.
4. S → B → F → D
Contains F. By Rule 4, B cannot be used if F is used → violation. Invalid route.
Thus, only three routes satisfy all constraints:
(1) S–A–C–D,
(2) S–B–C–D,
(3) S–A–E–D.
Final Answer: 3