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:

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

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search