Seven towns a, b,c, d, e, f, and g are connected by a system of highways as follows: (1) 1-22 goes from a to c, passing through b; (2) 1-33 goes from c to d and then passes through b as it continues to f; (3) 1-44 goes from d through e to a; (4) 1-55 goes from f to b, passing through g; and (5) 1-66 goes from g to d.
(a) Using vertices for towns and directed edges for segments of highways between towns, draw a directed graph that models this situation.
(b) List the paths from g to a.
(c) What is the smallest number of highway segments that would have to be closed down in order for travel from b to d to be disrupted?
(d) Is it possible to leave town c and return there, visiting each of the other towns only once?
(e) What is the answer to part (d) if we are not required to return to c?
(f) Is it possible to start at some town and drive over each of these highways exactly once? (You are allowed to visit a town more than once, and you need not return to the town from which you started.)