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.