In the first paper on Graph/Network Theory, written in 1736, Leonhard Euler considered the following problem:

The residents of the Town of Konigsberg (now Kalinigrad) had seven bridges over the Pregel River as schematically drawn below.

The question raised by Euler was: *Would it be
possible to start at any place in the town, cross each bridge exactly one
time, and return to the starting place?* Either construct such a tour
of Koningsburg or prove that it would be impossible to do so.

By constructing the graph below to represent the problem, Euler concluded that it was impossible.