The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Using Graph Theory to Count Routes

Date: 07/15/98 at 06:04:56
From: patrice blackman
Subject: Use a tree diagram or systematic list.

There is a rumor that Daddy Warbucks is planning to start a new 
airline. He plans to serve 5 cities: Atlanta, Boston, Chicago, Dallas 
and Erie. There will be direct flights between each pair of cities. 
Use a diagram or a list to show how many different routes this will 
create. (Remember that going from Atlanta to Boston is the same route 
as going from Boston to Atlanta). How many different routes are there?

Date: 07/24/98 at 10:20:07
From: Doctor Erra
Subject: Re: use a tree diagram or systemmatic list.

Hello Patrice,

Your question is in fact a question about a "complete graph." Let us 
see how it can be shown. For two cities you have one route:


This is called a graph with two vertices A and B and one edge (a route 
for you). It is "complete" because all vertices are "connected" by a 
route. When we say that "going from Atlanta to Boston is the same 
route as "going from Boston to Atlanta" this means that we have an 
"undirected graph." Going from A to B is the same "cost" (time, 
distance, money) as going from B to A.

With 3 cities, we have a triangle:

    \     /  
     \   /  
      \ /     

To answer your question, we'll start by considering the conjecture: are 
there n routes when we have n cities? No! Because for example, with 4 
cities you will have 6 routes. Make a picture with 4 cities A, B, C, D 
as the 4 corners of a square. There will be 4 sides plus 2 diagonals.

For 5 cities, make a picture with 5 points on a pentagon and show all 
routes. You will see that for n cities the number of routes is equal 
to ...? I leave you the exact computation. Remember, any of the n 
cities is connected to the (n-1) other cities, but since the graph is 
undirected, all of the routes are counted twice. This means that we 
must divide by 2.

Hope it helps,
- Doctor Erra, The Math Forum   
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.