Go Take a Hike!

The people of Konigsberg, Prussia were prone to taking walks after dinner.  Their town had the Pregel River running through, dividing the town into 4 land masses: one on each side of the river and two islands in the river.  The land masses were connected by 7 different foot bridges.  The people wondered, could they walk around and cross each bridge exactly one time each?  

When Leonhard Euler came into the picture, they no longer had to ask.  They knew!  You see, Euler turned it into a graph theory problem.  The land masses were represented with points called vertices, and the bridges were represented with segments or curves called edges.  It turns out that every land mass had an odd number of bridges coming out of it.  So, the graph had more than two odd vertices.  This tells us that it is impossible to take the walk that the Prussians wanted to take.  Always, a bridge would have to be used more than once in order to cross every bridge.  

We can thank Euler for not only solving this problem but developing the field of graph theory, which has many uses today.  Some instances where graph theory comes in handy?  Graphs can be used to map out family trees, train tracks, highways, data networks, and much more.  Local to me, an application has been the planning of walking paths at Bok Tower Gardens in Lake Wales, Florida.  The garden planners created a graph of the various points of interest and the paths that may be used.  They are striving to make this picturesque place more accessible to those with handicaps, and graph theory is a vital tool in that process.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s