Graph theory is one of the few branches of mathematics that may be said to have a precise starting date. In 1736, Leonhard Euler solved a celebrated problem, known as the Konigsberg bridges problem. The question had been posed whether it was possible to walk over all the seven bridges spanning the river pregel in Konigsberg just once without retracing one’s footsteps. Euler reduced the question to a graph theoretical problem, and found an ingenious solution. Euler’s solution marked not only the introduction of the discipline of graph theory but also the first applications of the discipline to a specific problem. Since its inception, graph theory has been exploited for the solution of numerous practical problems, and today still retains an applied character. In the early days, very important strides were made in the development of graph theory by the investigation of some very concrete problems, e.g. Kirchhoff’s study of electrical circuits, and Cayley’s attempts to enumerate chemical isomers. Also many branches of mathematics such as group theory, matrix theory, numerical analysis, probability and topology have their interaction with graph theory. It has also become more and more clear in recent years that the two disciplines of graph theory and computer science have much in common and that each is capable of assisting significantly in the development of the other.