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?
 A: 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:


*

*Konig's theorem

*Menger's theorem

*Max-flow min-cut

*The Birkhoff-von Neumann theorem

*Dilworth's theorem
A: 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. 
A: 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."
