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

Approach: List every directed S-to-E path first, then apply the node-count cap as a filter. With so few edges, full enumeration is fastest and safest.

Step 1: Trace all S-to-E paths.
From S you can go to A or B.
\( S \to A \to E \) (A has an edge to E) $-$ valid, 3 nodes.
\( S \to A \to C \to E \) $-$ 4 nodes.
\( S \to B \to C \to E \) (B only reaches C, C reaches E) $-$ 4 nodes.
There are no other directed paths.

Step 2: Apply the cap.
'A route cannot visit more than 3 nodes including S and E.' That bars both 4-node paths and keeps only the 3-node one.

Step 3: Count survivors.
Only \( S \to A \to E \) qualifies.

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

Answer 2

Approach: Since a route can include at most \(3\) nodes total (S, one possible stop, and E), the only routes to check are direct \(S\to E\) (no such edge exists) and two-hop routes \(S\to X\to E\) for each possible intermediate \(X\in\{A,B,C\}\).

Check each candidate \(X\):
\(X=A\): is \(S\to A\) an edge? Yes. Is \(A\to E\) an edge? Yes. So \(S\to A\to E\) is valid.
\(X=B\): \(S\to B\) exists, but \(B\to E\) is not in the edge list. Invalid.
\(X=C\): \(S\to C\) is not in the edge list at all (only \(A\to C\) and \(B\to C\) reach C). Invalid.

Any route through two intermediate hubs (like \(S\to A\to C\to E\)) would use \(4\) nodes, exceeding the \(3\)-node cap, so such routes don't count.

Only one route survives: \[ \boxed{S\to A\to E,\ \text{i.e. } 1 \text{ valid route}} \]