Master of Mathematics in Combinatorics and Optimization - Graph Theory

University of Waterloo

A graph consists of a set of elements together with a binary relation defined on the set. Graphs can be represented by diagrams in which the elements are shown as points and the binary relation as lines joining pairs of points. It is this representation which gives graph theory its name and much of its appeal. However, the true importance of graphs is that, as basic mathematical structures, they arise in diverse contexts, both theoretical and applied. The concept of a graph was known already to Euler in the early eighteenth century, but it was the notorious Four-Colour Problem, posed by F. Guthrie in the mid-nineteenth century, that spurred the development of this simple concept into a flourishing theory. In this century, interactions between graph theory and linear algebra, probability theory, number theory, group theory, geometry, topology, and other branches of mathematics have led to further developments in the subject. In recent years, its fundamental links with operations research and computer science have resulted in the fast growth and greatly increased prominence of graph theory.