A Brief History of Graph Theory
Euler's paper on the Seven Bridges of Königsberg was published in 1736. It is regarded as the first paper in the history of graph theory.
It was not until James Joseph Sylvester wrote a paper in 1878 that the term graph began to be associated with these structures. The first text book on graph theory, Theorie der endlichen und unendlichen Graphen (English edition here), was written by the Hungarian Dénes Kőnig (who at one time taught Paul Erdős) and published in 1936. The publication of this book effectively marked the beginning of Graph Theory as its own branch of mathematics. A later book, Graph Theory by Frank Harary, published in 1969, was reported by Martin Gardner to be "the definitive textbook on the subject" the world over. It enabled mathematicians, chemists, electrical engineers and social scientists to talk to each other.
The Wikipedia article about Graph Theory mentions some significant developments in the history of Graph Theory:
In 1857, the British mathematician, Arthur Cayley, studied a particular class of graphs called trees. His study had many implications in theoretical chemistry and marked the beginning of enumerative graph theory (which required the enumeration of graphs having particular properties). Cayley linked his results on trees with contemporary studies of chemical composition, and some of the standard terminology of graph theory dates from this fusion of ideas (between mathematics and chemistry).
In 1852, Francis Guthrie posed an interesting problem: When colouring any map in a plane (not on a globe), is it possible to colour all the regions with just four colours (so that no adjoining regions share the same colour)? This became famously known as the four color problem. Attempts to prove this true led to the development of other branches of number thoery (factorisation problems and extremal graph theory). The four color problem remained unsolved for more than a century. The proof finally came about using computers and really took place in stages, in that the earlier proofs were not fully accepted. You may read more in the Wikipedia articles about graph theory and the four color problem.
Some Applications of Graph Theory (Wikipedia Summary)
Many practical problems can be represented by graphs.
In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. For instance, the link structure of a website can be represented by a directed graph, in which the vertices represent web pages and directed edges represent links from one page to another. A similar approach can be taken to problems in travel, biology, computer chip design, and many other fields. The development of algorithms to handle graphs is therefore of major interest in computer science.
Since syntax and compositional semantics follow tree-based structures,the field of linguistics has been greatly influenced by graph theory. Modeling word meaning is easier when a given word is understood in terms of related words, so semantic networks are therefore important in computational linguistics. Much work has been done in understanding language as a graph. Phonology (which uses lattice graphs in optimality theory) and morphology (which uses finite-state transducers to analyse finite-state morphology) also benefit from this field of mathematics. Interestingly, organizations such as TextGraphs, as well as various 'Net' projects, such as WordNet, VerbNet, and others have sprung up due to the usefulness of graph theory to linguistics.
Graph theory is also used to study molecules in chemistry and physics. In condensed matter physics, the three-dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms. In chemistry a graph makes a natural model for a molecule, where vertices represent atoms and edges bonds. This approach is especially used in computer processing of molecular structures, ranging from chemical editors to database searching. In statistical physics, graphs can represent local connections between interacting parts of a system, as well as the dynamics of a physical process on such systems. Graphs are also used to represent the micro-scale channels of porous media, in which the vertices represent the pores and the edges represent the smaller channels connecting the pores.
Graph theory is also widely used in sociology as a way, for example, to measure actors' prestige or to explore the spreading of rumours, notably through the use of social network analysis software. Acquaintanceship and friendship graphs describe whether people know each other. Influence graphs model whether certain people can influence the behavior of others. Finally, collaboration graphs model whether two people work together in a particular way, such as acting in a movie together.
Graph theory is also useful in biology and conservation efforts where a vertex can represent regions where certain species exist and the edges represent migration paths, or movement between the regions. This information is important when looking at breeding patterns or tracking the spread of disease, parasites or how changes to the movement can affect other species.
In mathematics, graphs are useful in geometry and certain parts of topology such as knot theory. Algebraic graph theory has close links with group theory.
A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights, or weighted graphs, are used to represent structures in which pairwise connections have some numerical values. For example, if a graph represents a road network, the weights could represent the length of each road or the volume of traffic on it.