The best way to introduce GT is perhaps, the way my lecturer Ms.Radhika did — with the Konisberg Bridge Problem.

### The Seven Bridges of Königsberg

The **Seven Bridges of Königsberg** is a historically notable problem in mathematics. It goes like this.

Source:https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

The city of Königsberg in Prussia which is now known as Kaliningrad, Russia) was set on both sides of the Pregel River. It included two large islands — Kneiphof and Lomse. These landmasses were connected to each other, or to the two mainland portions of the city, by seven bridges, as shown in the actual map above.

**Problem Statement: **Plan a route through the city that would cross each of those seven bridges once and only once.

**Conditions:**

These are not allowed

Reaching an island or mainland bank other than via one of the bridges

Accessing any bridge without crossing to its other end

**Solution: **It’s at the end of the blog. Give it a few minutes thought.

### What does this have anything to do with Graph Theory?

Well, Euler observed that…

### 1. The choice of land route within each land mass is irrelevant.

This implied that the problem needn’t be viewed photographically or in a map, but can be expressed in an abstract form.

This kinda means you could chuck the map, draw each landmass as a dot or node, and the bridges as lines or curves. This also means you can bend this drawing in any way ( without breaking the lines/curves or removing anything) and the problem and solution would still be the same!

This transforms our problem as below

Sources: Wikipedia,Mvngu ,Brittanica

### 2. If one enters by a bridge, one must leave by a bridge.

Euler observed that except at the endpoints of the walk, when one enters a vertex by a bridge, one must exit the vertex by a bridge. That is the number of times one enters a non-terminal vertex equals the number of times one leaves it. Now, if every bridge can be walked upon just once, then for each vertex ( the non-terminal ones) ** the number of bridges touching that land mass must be even, that is the degree of each node should be even**(half of them towards,half away from the land)

He concluded that a necessary condition for the walk of the desired form is that the ** graph be connected and have exactly zero or two landmasses of odd degree**.

**( The degree refers to the number of bridges connected to it)**

*The rest must be of even degree.*But in our problem here, degree of a, b, c and d are 3. All nodes have odd degrees, which mean a solution is impossible.

There is no solution!A bit disappointing huh, but this problem laid foundation to the much-renowned Graph Theory. It took over 150 years for mathematicians to picture as a graph though.

So what is a graph?

### Some definitions:

A** Graph **is an ordered triplet G=(V(G), E(G), ψ(G)) consisting of *non-empty set* V(G) of vertices, a set E(G) of edges and an incidence function ψ(G) that associates with each edge of G with an un-ordered pair of vertices.

The definition means you can have a graph with no edges and just nodes, but the converse won’t be a graph.

To relate with the problem, the landmasses we saw in point 1 are the vertices, the bridges are the edges, a mapping function of both would be your ψ(G) and the entire figure is your graph.

**A simple graph** would be one with neither **self-loops**( the edge starts and ends on the same node) or **parallel edges**( edges that share the same nodes).

A graph would be **trivial** if it had just one **isolated node.**

Two vertices are said to be **adjacent** if they are the end vertices of the same edge.

When a vertex v is an end vertex of some edge e, then they are said to **incident** on each other.

That’s it folks. That’s how Graph Theory was first conceived. This is a humble introduction to GT.

#SevenBridgesProblem #Graph #GraphTheory #KonigsbergProblem #Programming