Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A river town has five land areas, , , , and , joined by ten bridges. There are two bridges between and and two between and . There is one bridge each for to , to , to , to , to and to . The figure shows the map as a multigraph.
Find how many land areas have an odd number of bridges. Can a visitor cross every bridge exactly once? Find the fewest new bridges that make such a walk possible, and the fewest that make a walk possible that also ends where it started.
A tree on vertices has edges; a forest with components has . Bipartite means no odd cycle; with no triangle, . A connected graph has an Euler circuit when all degrees are even, and an Euler trail when exactly two are odd.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. Degrees. : . : . : . : . : . The sum is .
Step 2. Odd areas. , , and : odd areas. The map is connected, but an Euler trail allows at most odd vertices, so no such walk exists now.
Step 3. One new bridge. A bridge from to makes both even, leaving and odd. Now an Euler trail exists, from to . One new bridge cannot leave fewer than odd areas, so is the fewest for a trail.
Step 4. A closed walk. All four odd areas must become even, and each new bridge fixes at most two of them. So at least bridges are needed, and to with to works.
Answer: odd areas; new bridge for a walk, for a closed walk.
Log in to join the discussion.
Loading…