Graph Theory with Applications [Repost]

It is no coincidence that graph theory has been independently discovered many times, since it
may quite properly be regarded as an area of applied mathematics.
The basic combinatorial nature of graph theory and a clue to its wide applicability are indicated
in the words of Sylvester, ‘‘The theory of ramification is one of pure colligation, for it takes no
account of magnitude or position ; geometrical lines are used, but have no more real bearing on the
matter than those employed in genealogical tables have in explaining the laws of procreation.’’
Indeed, the earliest recorded mention of the subject occurs in the works of Euler, and
although the original problem he was considering might be regarded as a somewhat frivolous
puzzle, it did arise from the physical world. Subsequent rediscoveries of graph theory by Kirchhoff
and Cayley also had their roots in the physical world.
Kirchhoff’s investigations of electric networks led to his development of the basic concepts and
theorems concerning trees in graphs, while Cayley considered trees arising from the enumeration of
organic chemical isomers. Another puzzle approach to graphs was proposed by Hamilton. After this,
the celebrated four colour conjecture came into prominence and has been notorious ever since.
In the present century, there have already been a great many rediscoveries of graph theory
which we can only mention most briefly in this chronological account.
Euler (1707–1782) became the father of graph theory as well as topology. Graph theory is con-
sidered to have begun in 1736 with the publication of Euler’s solution of the Konigsberg bridge prob-
lem. The graph theory is one of the few fields of mathematics with a definite birth date by ore.