Try It Now

Work these exercises to see how well you understand this material.

Answer:
1. A rough estimate of the number of vertices in the "world airline graph" would be the number of cities with a population greater than or equal to 100,000. This is estimated to be around 4,100. There are many smaller cities that have airports, but some of the metropolitan areas with clusters of large cities are served by only a few airports. 4,000-5,000 is probably a good guess. As for edges, that's a bit more difficult to estimate. It's certainly not a complete graph. Looking at some medium-sized airports such as Manchester, NH, the average number of cities that you can go to directly is in the 50-100 range. So a very rough estimate would be $\frac{75 \cdot 4500}{2} = 168,750$ . This is far less than 4,500², so an edge list or dictionary of some kind would be more efficient.
2. The number of ASCII characters is 128. Each character would be connected to $\binom{8}{2} = 28$ others and so there are $\frac{128 \cdot 28}{2} = 3,584$ edges. Comparing this to the 128² = 16,384, an array is probably the best choice.
3. The Oxford English Dictionary as approximately a half-million words, although many are obsolete. The number of edges is probably of the same order of magnitude as the number of words, so an edge list or dictionary is probably the best choice.
Answer: Each graph is isomorphic to itself. In addition, G₂ and G₄ are isomorphic; and G₃, G₅, and G₆ are isomorphic to one another.