Question

For a route that satisfies the above restrictions, which of the following statements is true?

• A. There is no route that satisfies the above restriction.
• B. A route can either start at C or end at C, but not both.
• C. D can be only an intermediate city in the route.
• D. The route has to necessarily end at E.
• A. One
• B. Zero
• C. Three
• D. Two

Answer 1

The Correct Option is C

We are given 5 cities: A, B, C, D, and E connected by 7 roads, with the requirement to start from any city and walk on each of the roads once and only once.
Additionally, we are not required to return to the city from which we started.
The key restrictions here involve ensuring that each road is walked exactly once, which is a classic problem related to Eulerian paths and circuits.
In an Eulerian path, every edge (road in this case) is visited exactly once, and such a path can only exist if the graph meets specific conditions:
- All vertices (cities) must have an even degree (for an Eulerian circuit), or exactly two vertices can have an odd degree (for an Eulerian path).
Let's analyze the degree of each city:
- City A has a degree of 3 (connected to B, C, and E).
- City B has a degree of 3 (connected to A, C, and E).
- City C has a degree of 3 (connected to A, B, and D).
- City D has a degree of 3 (connected to C, B, and E).
- City E has a degree of 3 (connected to A, B, and D).
Since all cities have an odd degree (3), this implies that there is no Eulerian circuit or path that satisfies the condition of visiting each road exactly once and only once without returning to the starting city.
Thus, statement (A) is false, and the correct answer is (C) D can be only an intermediate city because we are constrained by the city connections and odd degrees, meaning D must not be the start or end of the route.

Answer 2

Since all five cities (A, B, C, D, E) have an odd degree of 3, there is no Eulerian path possible in this graph (as explained in Q95).
In order to have an Eulerian path, the graph must have either exactly 0 or exactly 2 vertices with an odd degree.
However, in this case, all 5 cities have an odd degree, so there is no possible starting city from which we can walk all 7 roads exactly once.
Thus, the correct answer is (B) Zero since no starting city satisfies the given condition.