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:

   A----------B

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:

   A-------B
    \     /  
     \   /  
      \ /     
       C

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
  http://mathforum.org/dr.math/