Consider the K¨onigsberg bridge problem (cf. Fig. 10.6).
(a) Suppose that there existed a second bridge connecting the islands B and C, and also another bridge connecting the land areas A and D. Construct an Euler cycle that crosses each of the bridges exactly once.
(b) Suppose the bridge connecting the islands B and C has collapsed. Construct an Euler path, i.e., a path (not necessarily a cycle) that passes through each arc of the graph exactly once.
(c) Construct an optimal postman cycle assuming all arcs have cost 1.
