Graph Theory and the Konigsberg Bridge Problem

WHO IS THIS FAMOUS MATHEMATICIAN?

1. He is credited with discovering this formula:

VERTICES + FACES = __ DGES + 2

2. P __ zzles like the seven bridges of Konigsberg interested him and were part of a new branch of mathematics that he started called topology.

3. He had thirteen grandchildren and died while playing with a grandchild. He is said to have created mathematics with a baby on his __ap and children playing around him.

4. He contributed greatly to the foundations of every branch of advanced mathematics. One of his famous equations is:

5. So numerous were his mathematical manuscripts that 200 volumes will be __equired to organize them into book form. He wrote 800 pages a year of high quality mathematics.

6. His name is Leonard __ __ __ __ __ .
1 2 3 4 5

For each of the following diagrams, fill in the chart on the next page and

(1) Tell how many odd and even vertices the figure has and

(2) Determine whether you can draw each design without retracing a line or lifting the pencil.

If the figure can be redrawn, give the starting and ending points.

Odd vertices are those points which have an odd number of lines / curve segments connecting to it.

Even vertices are those points which have an even number of lines / curve segments connecting to it.

Can you go through each door in the following house plans exactly once?
Consider each room as a vertex and the outside as one vertex.

Figure #	Number of Even Vertices	Number of Odd Vertices	Can it be Redrawn? Start? Stop?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

What is the common characteristic of the figures that can be drawn? _________________

Hint: The answer depends only on the number of ODD vertices in the diagram.
The number of even vertices has no bearing on whether a figure can be redrawn.

Now apply what you have learned to the Konigsberg Bridge Problem that Leonard Euler solved.

Here is a map of Konigsberg, Prussia, which is now called Kaliningrad, Russia.

First, identify the two islands and the two main banks of the city and the river Pregel and the 7 bridges. Then replace each land mass by a vertex and each bridge by a line / curved segment.

This network is similar to the diagrams #1 — 12 above.

How many EVEN vertices does the figure have? __________

How many ODD vertices does the figure have? __________

Can it be redrawn? __________