## Introduction

The ancient town of Königsberg was divided into four land masses by the river Pregel. Seven bridges connected these land masses. The people of Königsberg created a game to find a path that would allow them to walk all over the town crossing the seven bridges exactly once. This problem came to be known as the Seven Bridges of Königsberg.

In this article, we will discuss the solution to the Königsberg Bridge problem and its implementation in C++ and Java.

## Königsberg Bridge Problem

Our story starts in the 18th century, in a town on the banks of the Pregel River. This town was called Königsberg. The river split the town into Four distinct regions which were connected by Seven Bridges. The people of Königsberg liked to walk around the city. They created a game among themselves- **Find a path that would allow them to cover all four regions using the seven bridges but - each bridge should be crossed exactly once****. **

You can find the above image __here__.

The famous mathematician Leonhard Euler was asked to solve this puzzle. Even though this puzzle had nothing to do with mathematics, he found it interesting enough to pursue it. This puzzle was found to be related to a topic - Geometry of Positions or what we call today the Graph Theory. So, we can say this problem birthed the Graph Theory.

Euler divided the problem into small parts. He viewed the four land regions as the four nodes and named them A, B, C, D and the seven bridges as the edges connecting these nodes.

This was the first time someone had used this kind of representation which we now call a Graph.

Euler used this Geometry of Positions and gave a negative solution to this problem i.e.**walk through ****Königsberg was NOT possible.**

### Are you pondering how did he conclude that no path exists?

As mentioned, Euler viewed the four land masses as vertices (A, B, C, D) and the seven bridges as the edges. 3 bridges join to the land mass A, 3 to B, 5 to C and 3 D. All the four vertices have an odd number of edges (bridges) connected to them and are called Odd Vertices.

Euler worked out that in order for a vertex to be an odd vertex, it should either be a starting vertex or a destination vertex (like if it had only 1 edge, given that we can traverse the edge only once, we can either start from that vertex or finish at that vertex but we cannot turn back and reach the same vertex). Since there can be only one beginning vertex and one ending vertex, there can be only two odd vertices so that we can traverse all the vertices only once, but in this problem, there are 4 odd vertices, hence no path exists!

While solving this problem, Euler came up with some interesting graph traversal techniques - Euler’s Path and Euler’s cycle.

### Euler’s Path

Euler’s path is a path that visits every edge in a graph exactly once.

### Euler’s Cycle

Euler’s cycle is an Euler’s path that starts and ends at the same vertex.

*Euler said that even though the Seven Bridges of Königsberg cannot be solved, there are some other graphs that can be traversed completely by going over each edge exactly once or simply said that there can be graphs that can have an Eulerian Path*.

To check if there exists an Eulerian Path, any *one* of the following conditions must be true -

1️⃣ Two vertices are odd vertices i.e.two vertices have an odd degree.

2️⃣ All of the vertices in the connected graph are of an even degree.