Graph theory is the study of networks. Networks can be defined by nodes and connections between nodes. Formally, a graph (V,E) is a collection of vertices V with a set of edges in V x V.

A graph G is called planar if G can be embedded in the plane so that no two edges intersect.
Euler’s Theorem states that for a connected non-empty, planar graph G, that V – E + F = 2, where V is the number faces, E is the number of edges, and F is the number of faces, which are regions bounded by edges.

More generally, given a n-torus, (or a surface of genus n), meaning the surface has n holes in it, V – E + F = 2 – 2n. So, for a torus, Euler’s Theorem states that V – E + F = 0.

The Four Color theorem says that any map can be colored with four colors. Kempe originally proved this theorem in 1879 but Heawood found a flaw was found with his proof. A century later, Haken and Appel proved the theorem by splitting the proof into over one thousand cases and using a supercomputer to check them all.

One problem of interest is: For some fixed choice of subgraph H, what is the maximum number of edges G can have to not contain H as a minor? A minor of a graph G is a graph obtained from G by first deleting some edges and vertices, and then contracting some edges. We say uv is an edge contraction if we replace u and v by a single vertex w, and connect w to all of the neighbors of u and v.

For instance, the maximum number of edges G can have to not contain a triangle is floor of n^2/2. This maximum is achieved by splitting the vertices into a group of n/2 and n/2 (or as evenly as possible), and forming the complete bipartite graph between these two sets. This is known as Mantel’s Theorem.