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

Approach: Only four routes are even offered — so don’t hunt for new paths; just run each candidate route through the four rules and keep the survivors.

Step 1: S \to A \to C \to D. No repeated node, \(3\) edges (within the limit), uses C but not E (Rule 3 fine), uses A not B/F (Rule 4 fine). Valid.

Step 2: S \to B \to C \to D. No repeat, \(3\) edges, uses C not E, uses B but not F. Valid.

Step 3: S \to A \to E \to D. Uses E; Rule 3 only forbids C alongside E, and this route has no C. No repeat, \(3\) edges. Valid.

Step 4: S \to B \to F \to D. Uses both B and F; Rule 4 forbids B whenever F is used. Invalid.

Count. Three routes clear every rule. \[ \text{Valid routes} = 3. \]

Final Answer: 3 (option 1).

Answer 2

Approach: Rebuild the possible routes directly from the allowed edges (S→A, S→B, A→C, B→C, A→E, B→F, C→D, E→D, F→D, the network implied by the four listed paths), then apply the two rules that can actually cut a route.

Step 1: Branch from S. Only two exits from S: to A or to B.

Step 2: Continue from A. From A, the route can go to C (giving S→A→C→D) or to E (giving S→A→E→D). Both are 3-edge routes, no repeats, both pass Rules 1 and 2.

Step 3: Continue from B. From B, the route can go to C (giving S→B→C→D) or to F (giving S→B→F→D).

Step 4: Apply Rule 3 (no C with E) and Rule 4 (no B with F). The two C-routes never meet E, so Rule 3 removes nothing; the E-route has no C either, so it survives Rule 3 too. But S→B→F→D uses both B and F together, Rule 4 removes exactly this one route.

Step 5: Count survivors. Of the 4 constructed routes, 1 is removed:
\[ 4 - 1 = 3 \]

Final Answer: 3 (option 1).