What are the most important results in graph theory?

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

-
I think this should be made community wiki, perhaps with one result per answer. –  Anthony Labarre Mar 11 '11 at 10:40
I would like to but there is no option available. –  Pratik Deoghare Mar 11 '11 at 10:46
I am slightly skeptical about this question, although I left an answer. Do you want this to just turn into a list of everyone's favorite results in graph theory (which is trivial to generate: just go through any good book), or do you want to actually give some criteria for what counts as "important"? –  Qiaochu Yuan Mar 11 '11 at 11:02
I want a list of most frequently used results. In the books on graph theory there are thousands of theorems and I am not sure which ones of those I should give importance to. –  Pratik Deoghare Mar 11 '11 at 11:15
"Mathematicians" is an enormous group of people, some of whom are graph theorists and may use all of the results in your books. –  Qiaochu Yuan Mar 11 '11 at 11:59

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."

-
or more generally, robertson-seymour en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem –  yoyo Mar 11 '11 at 15:12

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.

-
Someone care to explain the downvote? –  Qiaochu Yuan Mar 11 '11 at 12:00
is not the Euler formula state: $V - E + F = 2$ not $1$? –  M.M Jul 21 at 13:48
@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. –  Qiaochu Yuan Jul 21 at 19:51

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:

-