Graph theory is the branch of mathematics that concerns itself with graphs.

The concept of graphs is extraordinarily simple, which explains their wide applicability. It is usually agreed upon that graph theory proper was born in 1736, when Euler formalized the now-famous “bridges of Königsberg” problem. Graph theory has now grown to touch almost every mathematical discipline, in one form or another, and it likewise borrows from elsewhere tools for its own problems. Anyone who delves into the topic will quickly see that the lifeblood of graph theory is the abundancy of tricky questions and clever answers. There are, of course, general results that systematize the subject, but we also find an emphasis on the solutions of substantial problems over building machinery for its own sake.

Graph theory representation of Königsberg bridges problem

For quite long graph theory was regarded as a branch of topology concerned with -dimensional simplices, however this view has faded away. The only remainder of the topological past is the topological graph theory, a branch of graph theory that primarily deals with drawing of graphs on surfaces. The most famous achievement of topological graph theory is the proof of the four-color conjecture (every political map on the surface of a plane or a sphere can be colored into four colors given that each country consists of only one piece).

Now, a (finite) graph is usually thought of as a subset of pairs of elements of a finite set (called vertices), or more generally as a family of arbitrary sets in the case of hypergraphs. For instance, Ramsey theory as applied to graph theory deals with determining how disordered can graphs be. The central result here is the Ramsey's theorem which states that one can always find many vertices that are either all connected or disconnected from each other, given that the graph is sufficiently large. The other result is Szemerédi regularity lemma.

The four-color conjecture mentioned above is one of the problems in graph coloring. There are many ways one can color a graph, but the most common are vertex coloring and edge coloring. In these type of colorings, one colors vertices (edges) of a graph so that no two vertices of the same color are adjacent (resp. no edges of the same color share a common vertex). The most common problem is to find a coloring using the fewest number of colors possible. Such problems often arise in scheduling problems.

Graph theory benefits greatly from interaction with other fields of mathematics. For example, probabilistic methods have become the standard tool in the arsenal of graph theorists, and random graph theory has grown into a full-fledged branch of its own.