Question

A delivery network allows routes from Start (S) to End (E) through intermediate hubs A, B, C.
Allowed edges:
S→A, S→B, A→C, A→E, B→C, C→E.
A route cannot visit more than 3 nodes including S and E.
How many valid routes from S to E are possible?

Hint:

When route length is restricted, always filter paths by allowed depth before checking connectivity. This avoids counting valid-looking but over-length paths.

Answer 1

Correct Answer: 1

We list all valid directed paths from S to E with at most 3 total nodes (including S and E). Thus, the route may have: \[ \text{Length 2: } S \to E \quad (\text{but no direct edge exists}) \] \[ \text{Length 3: } S \to X \to E \] Step 1: Check all 2-node direct paths. 
There is no direct edge S→E. So, no valid length-2 route. 
Step 2: Check all 3-node paths of the form: \[ S \to X \to E \] We test all outgoing nodes from S: 
From S→A: A→E exists. 
Valid path: \[ S \to A \to E \] 
From S→B: B→E does not exist. 
So B cannot reach E within one more step. 
From S→(other nodes): No other outgoing edges. 
Step 3: Check whether 4-node routes are allowed. 
The problem states: 
“A route cannot visit more than 3 nodes including S and E.” Therefore, 4-node paths (like S→A→C→E) are forbidden.
Thus, only 3-node paths are allowed. 
Final Count: Only one valid short route exists: \[ S \to A \to E \] Final Answer: \(\boxed{1}\)