Browse and Search the Library
: Math Topics
: Discrete Math
: Graph Theory
Library Home ||
Full Table of Contents ||
Suggest a Link ||
(see also All Sites in this category)
- The Bridges of Königsberg - Isaac Reed
This problem inspired the great Swiss mathematician Leonard Euler to create graph theory, which led to the development of topology.
- The Four Colour Theorem - MacTutor Math History Archives
Linked essay describing work on the theorem from its posing in 1852 through its solution in 1976, with two other web sites and 9 references (books/articles).
- Graph Theory - Dave Rusin; The Mathematical Atlas
A short article designed to provide an introduction to graph theory. A graph is a set V of vertices and a set E of edges - pairs of elements of V. This simple definition makes Graph Theory the appropriate language for discussing (binary) relations on sets. Among the topics of interest are topological properties such as connectivity and planarity (can the graph be drawn in the plane?); counting problems (how many graphs of a certain type?); coloring problems (recognizing bipartite graphs, the Four-Color Theorem); paths, cycles, and distances in graphs (can one cross the Königsberg bridges exactly once each?). Many graph-theoretic topics are the object of complexity studies in computation (e.g. the Travelling Salesman problem, sorting algorithms, the graph-isomorphism problem). The theory also extends to directed, labelled, or multiply-connected graphs. History; applications and related fields and subfields; textbooks, reference works, and tutorials; software and tables; other web sites with this focus.