The Connections Project

Graph Theory

The connection between graph theory and real analysis arises when the planarity of graphs is considered. A planar graph is one which can be embedded into 2-dimensional Euclidean space such that no two edges cross. Considered as abstract vertex- and point-sets, it makes no sense to talk about edges intersecting each other.

There is an entire field called algebraic graph theory. For example, graph theory naturally gives rise to questions of symmetry, and these are best explored with the machinery of group theory.

The relatively mundane study of graph planarity in the plane, explodes into an amazing mind-bending circus of results when you start embedding graphs into more exotic spaces like the torus, the Klein bottle, the Mobius strip, or more exotic surfaces.

Many of the prototypical NP-hard problems studied in complexity theory involve graphs: the Traveling Salesman Problem, for example.

One interesting and elementary connection between model theory and graph theory is the proof of the four color mapping theorem in the case of infinite graphs. Assuming the theorem in the finite case, the infinite case is a simple matter of applying the compactness theorem of model theory.

Graph theorists use matrices to encode data about their graphs, and then the full arsenal of linear algebra can be applied toward optimizing graph theoretical computations. This happy marriage of theories has a very real effect on all of our lives; every time you search a query in Google, linear algebra and graph theory conspire to give you the best results.