### Brain Teasers

# Ferry Routes

XYZ Ferries, in a move to enter the profitable Mediterranean tourism industry, has just opened new stops and routes at Caligari, Monaco, Civitavecchia, and Palermo. There are two routes between Caligari and Monaco, two routes between Palermo and Caligari, a route between Civitavecchia and Monaco, a route between Civitavecchia and Caligari, and a route between Civitavecchia and Palermo.

To promote these ferry routes, XYZ Ferries has decided to make the first ride on one single route free for each person. When a friend hears about the promotions, he bets that you cannot ride every single ferry route without paying a single euro or using another mode of transportation. After mulling it over, you determine that it would be impossible to win the bet. You offer to accept the bet if you could theoretically create another ferry route. He claims that would be too easy and forces you to start in Monaco and end in Caligari. You accept the bet knowing that you will win. Where would you put this new route?

To promote these ferry routes, XYZ Ferries has decided to make the first ride on one single route free for each person. When a friend hears about the promotions, he bets that you cannot ride every single ferry route without paying a single euro or using another mode of transportation. After mulling it over, you determine that it would be impossible to win the bet. You offer to accept the bet if you could theoretically create another ferry route. He claims that would be too easy and forces you to start in Monaco and end in Caligari. You accept the bet knowing that you will win. Where would you put this new route?

### Hint

Draw out the ferry lines and their ports. All other geographical information is irrelevant.### Answer

You add another route from Civitavecchia to Palermo, and your astonished friend gives you the money and listens to your explanation.First, you simplify everything into a graph. The graph has vertices, or ports, and edges, or the ferry routes. You give each vertex a degree, or the number of edges that lead to the vertex. Using this information, you deduce that a path that visits every edge in a graph needs an edge in and an edge out, expect for the start and finish, which only need one edge. Therefore, you conclude that all points expect for the start and finish need an even numbered degree in order for the path to finish. In this problem, you only need to make Civitavecchia and Palermo have an even number of edges leading to them. The two vertices already have three edges each leading to them, so you just add a fourth edge between the two cities to make the degree number even and complete the bet.

Hide Hint Show Hint Hide Answer Show Answer

## What Next?

View a Similar Brain Teaser...

If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.

### Solve a Puzzle

Comments hidden to avoid spoilers.

## Follow Braingle!