Question

A courier must travel from Hub S to Hub T using intermediate hubs A, B, C.
Allowed edges: S→A, S→B, A→C, B→C, C→T, A→T.
The courier cannot use more than 3 edges in total.
How many valid routes from S to T are possible?

Hint:

When edge limits are imposed, always classify possible routes by path length (1-edge, 2-edge, 3-edge, etc.) and test each systematically.

Answer 1

Correct Answer: 3

We list all possible directed paths from S to T with at most 3 edges. The allowed edges are: \[ S\to A,\ S\to B,\ A\to C,\ B\to C,\ C\to T,\ A\to T \] Step 1: Count routes that use exactly 1 edge.
A 1-edge route would be a direct edge S→T.
No such edge exists.
So 0 routes.
Step 2: Count routes that use exactly 2 edges.
These are paths of the form: \[ S \to X \to T \] Check each outgoing node from S:
- From S→A: second edge A→T exists → valid route \[ S \to A \to T \] - From S→B: there is no B→T → invalid
Thus there is exactly 1 route of length 2. Step 3: Count routes that use exactly 3 edges.
These are paths of the form: \[ S \to X \to Y \to T \] Check all possible chains:
- From S→A:
A→C→T is valid.
Route:
\[ S \to A \to C \to T \] - From S→B:
B→C→T is valid.
Route: \[ S \to B \to C \to T \] No other 3-edge directions exist.
Thus there are 2 routes of length 3.
Step 4: Total valid routes. \[ 0 + 1 + 2 = 3 \] Final Answer: \(\boxed{3}\)