Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
"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

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

share|improve this answer
    
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.

share|improve this answer
3  
Someone care to explain the downvote? –  Qiaochu Yuan Mar 11 '11 at 12:00

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:

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.