ABSTRACT
Although generally regarded as one of the more modern branches of mathematics, graph theory actually dates back to 1736. In that year Leonhard Euler† published the first paper on what is now called graph theory. In the paper, Euler developed a theory which solved the so-called Ko¨nigsberg Bridge problem (see §11.2). Surely few other branches of the subject can be given as precise a ‘birthday’ as this. However, it must be said that, as a mature subject, graph theory is indeed modern. It came of age, so to speak, exactly 200 years after Euler’s paper with the publication in 1936 of the first text in graph theory. (The first 200 years of graph theory are beautifully outlined in Biggs et al (1976) which includes extracts from many of the original papers concerned with the development of graph theory.)
Like many of the concepts we have considered, the idea of a graph is very simple. It is probably due to its simplicity that graph theory has found many applications in recent years in fields as diverse as chemistry, computer science, economics, electronics and linguistics.
