Directions for the following 3 (three) items: Consider the given information and answer the three items that follow.
Eight railway stations A, B, C, D, E, F, G and H are connected either by two-way passages or one-way passages. One-way passages are from C to A, E to G, B to F, D to H, G to C, E to C and H to G. Two-way passages are between A and E, G and B, F and D, and E and D.
In how many different ways can a train travel from F to A without passing through any station more than once?
Answer & explanation
Answer: (d) 4
From F the only exit is D, and from D the train can go to E or H. Through E it reaches A directly, via C, or via G and C (3 routes); through H it must go to G, then C, then A (1 route). That makes 4 routes.
- Exits from each station: A → E; B → F, G; C → A; D → H, F, E; E → G, C, A, D; F → D; G → C, B; H → G.
- F's only exit is D.
- D → E: then E → A (F-D-E-A), E → C → A (F-D-E-C-A), or E → G → C → A (F-D-E-G-C-A). E → G → B leads only back to F or G, already used.
- D → H: H → G, then G → C → A (F-D-H-G-C-A); G → B leads back to F — a dead end.
- Total routes without repeating a station = 3 + 1 = 4.
Remember · Count routes with a tree: branch at every station and prune any branch that revisits a station or reaches a dead end.
Question and answer: UPSC's official GS Paper II (2017, Series A) — paper ↗ · answer key ↗. Explanation: Minimalist IAS, checked 30 Sept 2026 (how we verify). ·