In Fantasia the airline system is organized in such a way that every city is connected to not more than three others, but even so it is possible to get from one city to another without making more than one change-over.
What is the maximum number of cities in Fantasia?
taken from
http://www.geocities.com/CapeCanaveral/Lab/4661/
2007-10-27 14:30:40 · 1 answers · asked by Mugen is Strong 7 in Science & Mathematics ➔ Mathematics
10 is the maximum number of cities. The Peterson Graph is a graph that achieves this. It is basically a pentagram inside a pentagon. The attached link gives a nice picture.
To see that 10 is the maximum number, note that if we start with a given city, c, it can be connected three others which can be connected to two others (they are already connected to c). So that gives you 1 + 3 + 2*3 = 10 total cities.
2007-10-27 19:41:17 · answer #1 · answered by Phineas Bogg 6 · 3⤊ 0⤋