Previous | ToC | Next Labs: Graph Theory. Part 1. Math Alive

Euler's Theorem

By solving the Konigsberg bridges problem Euler started a new branch in mathematics — Graph Theory.

Euler's argument goes as follows:

If a particular island or a river bank is not your starting or ending point, you have to enter it by a bridge and leave by another bridge. That means that the total number of bridges to this island or river bank must be even. Only a starting or an ending landmass can have an odd number of bridges connected to it. Hence no more than two landmasses can have an odd number of bridges if we are able to make the tour. In the particular case of Konigsberg each of the four landmasses has an odd number of bridges connecting to it. This means there is no tour that uses each bridge exactly once.

Previous | ToC | Next Last Modified: August 2008