Introduction to graphs

The introduction of graphs and the associated graph theory is widely attributed to Leonhard Euler in 1736 when he worked on the problem of the Seven Bridges of Königsberg (https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg).

The city was divided by the Pregel river which at some point formed two islands, and seven bridges were built according to the layout shown in the following diagram. The problem was to find a way for a person to walk across each and every bridge once and only once and come back to the starting point. Euler proved that there was no solution to this problem and while doing this gave birth to graph theory. The fundamental idea was to transform the city diagram into a graph where each land mass is a vertex, and each bridge is an edge that linked two vertices (that is, land mass). The problem was then reduced to finding a path, which is a continuous sequence of edges and vertices, that contains each and every bridge only once.

The following...