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

Approach: A small directed graph with at most 3 edges $-$ just trace every S-to-T path along the allowed arrows by length. The graph is acyclic, so there is nothing to repeat.

Step 1: List the arrows.
\[ S\to A,\quad S\to B,\quad A\to C,\quad B\to C,\quad C\to T,\quad A\to T. \]

Step 2: Length-1 paths.
A direct \(S\to T\) arrow? None. So 0 routes.

Step 3: Length-2 paths \(S\to X\to T\).
From \(S\to A\): is there \(A\to T\)? Yes. Route \(S\to A\to T\). From \(S\to B\): is there \(B\to T\)? No. So 1 route.

Step 4: Length-3 paths \(S\to X\to Y\to T\).
\(S\to A\to C\to T\) $-$ valid. \(S\to B\to C\to T\) $-$ valid. No other chains reach T in 3 hops. So 2 routes.

Step 5: Add up.
\[ 0 + 1 + 2 = \boxed{3}. \]

Final Answer: \(\boxed{3}\)

Intuition: with a tiny acyclic graph and a 3-edge cap, organising the search by path length guarantees you miss nothing and never double-count.

Answer 2

Approach: List every path outward from S, stopping any branch once it reaches T or exceeds 3 edges, then simply count the survivors.

Step 1: From S, the only edges are S→A and S→B.

Step 2 (via A): From A: A→C or A→T.
  S→A→T uses 2 edges – a complete, valid route.
  From C the only edge onward is C→T, giving S→A→C→T with 3 edges – valid.

Step 3 (via B): From B, the only edge is B→C.
  S→B→C→T uses 3 edges (C→T closes it) – valid.
  There is no edge from B directly to T, so no shorter route through B exists.

Step 4: No path in this graph ever exceeds 3 edges anyway, so the edge-limit rule never actually eliminates anything here, it only confirms all found routes qualify.

Final Answer: 3 valid routes (S→A→T, S→A→C→T, S→B→C→T).