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

Step 1: Work backward from the destination. The only edges into T are A→T and C→T, so anything reaching T must arrive via A or via C.
Step 2: Count ways to reach A from S: only S→A (1 edge). Count ways to reach C from S: via S→A→C or S→B→C (2 edges each), so 2 ways to be at C using 2 edges.
Step 3: Add the final edge to T: from A directly (1 way, 2 edges total) and from C directly (2 ways, 3 edges total, within the 3-edge cap).
\[ 1 + 2 = \boxed{3} \]
Final Answer: 3 valid routes.