8
$\begingroup$

What are the theorems/results/widely applicable results in graph theory that everyone should know about?

  • 1
    "Mathematicians" is an enormous group of people, some of whom are graph theorists and may use _all_ of the results in your books. โ€“ 2011-03-11

3 Answers 3

7

Hall's marriage theorem is widely applicable. Remarkably it happens to be equivalent to other theorems in graph theory and combinatorics which are also widely applicable:

4

Euler's formula $V - E + F = 1$ for planar graphs is extremely important; in some sense it motivated much of modern topology. (An excellent introduction to this thesis is Richeson's book Euler's Gem.) It also leads to a reasonably short proof of the classification of the Platonic solids, so even before generalization, it's quite important. The generalization to graphs on surfaces is used to prove the easy direction of the Heawood conjecture.

Of course nowadays it is recognized that Euler's formula is really a statement about triangulations of the sphere, and the generalization to triangulations of arbitrary manifolds and other characterizations of Euler characteristic is fundamental.

The Geometry Junkyard has a nice list of nineteen proofs of Euler's formula. One of them uses another basic and useful fact about graphs, which is that they always have spanning trees. This is used, for example, in topology to prove that the geometric realization of a graph is homotopy equivalent to a wedge of circles, which shows that subgroups of free groups are free.

  • 0
    @M.M: that's Euler's formula for convex polyhedra. The difference between this and Euler's formula for planar graphs comes down to whether you think the "face at infinity" of a planar graph (the complement of the interior) counts as a face. Said another way, it depends on whether you think a planar graph encodes a CW decomposition of a disk or a sphere. โ€“ 2015-07-21
3

Kuratowski's and Wagner's theorems which give necessary and sufficient conditions for a finite graph to be planar.

I should add that it's certainly possible to argue that these are actually theorems of topology rather than graph theory.

For a simple proof of the non-planarity of $K_{3,3}$ and $K_5$ one can consult Munkres's Topology 2nd ed. ยง64 and at the end of the section he notes "It is a remarkable theorem, due to Kuratowski, that the converse is also true! The proof is not easy."

  • 0
    or more generally, robertson-seymour http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem โ€“ 2011-03-11