design a route?

Question

http://img147.imageshack.us/my.php?image=routeue4.jpg

There are five cities A,B,C,D and E connected by seven roads as shown in the figaure below..

Design a route such that you start from any city of your choice and walk on each of the seven roads once and only once,not necessarily returning to the city from which you started.

Q: For aroute that satiesfies 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.



whats the answer ?

can you find such a route really ? please show me the graph .

thanks

---------------------------
hi, guys....but you guys are passing through the same point C ?is this not violating the restriction ?

n.b: Answer is (b) ...its given in the book.

Answer 1

The true answer is b: A route can either start at C or end at C, but not both.
Answer a is wrong since there are many routes that satisy the restriction, For example:
D--> B--> E--> D--> C--> A--> B--> C, or
C--> D--> E--> B--> A--> C--> B--> D, and many others.

Answer c is wrong since, as shown by the two examples above, D can be also the first or the last city in the route.

And Answer d is wrong, since as also shown by the two examples, the route has not to necessarily end at E, but also at other cities such as C and D.

So how is answer b correct? try to make a route that starts at C, such as the one shown in the second example, and the route will never end at C, but will end at either A or D.

Answer 2

Answer is B) it can either start, or end at C, but not both.

The same with D. Actually it must i) start at C and end at D, or ii) start at D and end at C.

One Route that starts at C and ends at D(reversing will give a route that ends at C and starts at D):
CABCDEBD

Why must it either start or end at C, and why can't it do both?

There are 3 roads out from C (or in, if you reverse). Assume that you start at C, and take one road. There are still two more roads that end at C, that you haven't taken. If you cover all of the roads (and none more than once), you must go back to C on a road that you didn't take the first time. Now there is still one road from C that you haven't taken (and only one), so you must take it. Now you have taken all the roads that lead to C, and you are no longer at C. Therefore you can't get back to C (thus you can't end there) unless you travel over a road a second time. Therefore you can either start or end at C, but not both. The same logic works for D.


Why must you either start or end at C?

Assume that you don't start at C. You must go through C at some point. To get to C, you have to take one of the three roads. Now you must take one of the other two remaining roads (to take all of the roads). So you take one of those. That leaves one (and only one) road left to C. Eventually you must take this road to get to C. Once you take this road, you can't leave C. So you must have ended at C.

The same logic can work for D.

Answer 3

Answer :

b. A route can either start at C or end at C, but not both.

Route:
C -> A -> B -> C -> D -> B -> E -> D

Answer 4

start at C end at D
E is second last
the route must start at C
C B D C A B E D