Introduction

 

The development of graph theory is very similar the development of probability theory, where much of the original work was motivated by efforts to understand games of chance. The large portions of graph theory have been motivated by the study of games and recreational mathematics. Generally speaking, we use graphs in two situations. Firstly, since a graph is a very convenient and natural way of representing the relationships between objects we represent objects by vertices and the relationship between them by lines. In many situations (problems) such a pictorial representation may be all that is needed. Example of such applications are chemical molecule and map coloring as shown in the diagrams below. Other examples are signal-flow graphs, Konigsberg bridges, tracing maze etc.

 

 

 

 

Secondly, we take the graph as mathematical model, solve the appropriate graph-theoretic problem, and then interpret the solution in terms of the original problem. This modeling procedure can be illustrate as follows:

 

Diagram

 

Most problems in graph theory can be described under the following headings:

 

For example, we may consider the following questions in investigating the Konigsberg bridges problem.

 

 

Existence Problems

Many of the existence problems in graph theory arose a recreational puzzles.

 

Construction Problems

 

 

History of Graph Theory

The origin of graph theory can be traced back to Euler's work on the Konigsberg bridges problem (1735), which subsequently led to the concept of an Eulerian graph. The study of cycles on polyhedra by the Thomas P. Kirkman (1806 - 95) and William R. Hamilton (1805-65) led to the concept of a Hamiltonian graph.

The concept of a tree, a  connected graph without cycles, appeared implicitly in the work of Gustav Kirchhoff (1824-87), who employed graph-theoretical ideas in the calculation of currents in electrical networks or circuits. Later, Arthur Cayley (1821-95), James J. Sylvester(1806-97), George Polya(1887-1985), and others use 'tree' to enumerate chemical molecules.

The study of planar graphs originated in two recreational problems involving the complete graph K5 and the complete bipartite graph K3,3. These graphs proved to be planarity, as was subsequently demonstrated by Kuratowski. First problem was presented by A. F. Mobius around the year 1840 as follows

Once upon a time, there was a king with five sons.
In his will  he stated  that  after  his  death the sons
should  divide  the  kingdom into  five provinces so
that  the  boundary  of  each  province should have
a  frontiers  line  in  common with each of the other
four provinces.

Here the problem  is whether one can draw five mutually neighboring regions in the plane.

The king further stated that all five brothers should
join  the provincial capital by roads so that no two
roads intersect.

Here the problem is that deciding whether the graph K5 is planar.

The origin of second problem is unknown but it is first mentioned by H. Dudeney in 1913 in its present form.

The puzzle is to lay a water, gas, and electricity
to  each  of  the  three  houses without any pipe
crossing another.

This problem is that of deciding whether the graph K3,3 is planar.

The celebrated four-color problem was first posed by Francis Guthrie in 1852. and a celebrated incorrect "proof" by appeared in 1879 by Alfred B. Kempe. It was proved by Kenneth Appel and Wolfgang Haken in 1976 and a simpler and more systematic proof was produced by Neil Roberton, Daniel Sanders, Paul Seymour, and Robin Thomas in 1994.