| Theorems from Graph Theory (MSC2010: 05C)
This is a subset of the complete theorem list for the convenience of those who are looking for a particular result in graph theory.
To see how this area fits into mathematics as a whole you can consult the Mathematics Subject Classification. Dave Rusin's Atlas entry is also valuable. There will inevitably be theorems which could appear here but don't and those which might be felt to belong elsewhere. I welcome comments.
Numbers in brackets are those from the complete listing.
1 (1) The Four-Colour Theorem
2 (12) The Matrix Tree Theorem
3 (24) Kuratowski's Theorem
4 (25) Wagner's Theorem
5 (26) Euler's Formula
6 (48) Beineke's Theorem on Line Graphs
7 (28) Ramsey's Theorem
8 (46) Cameron's Theorem on Distance-Transitive Graphs
9 (50) The Euler-Hierholzer "Bridges of Königsberg" Theorem
10 (52) The Robertson-Seymour Graph Minor Theorem
11 (60) The Strong Perfect Graph Theorem
12 (70) Graph Colouring by Vertex Degree (a Theorem
under construction!)
13 (80) 1-factorisation of Regular Graphs (a Theorem
under construction!) Colour-free version here.
14 (94) Cayley's Formula
15 (117) A theorem of Erdős and Wilson on Edge Colouring
16 (119) Kneser's Conjecture
17 (120) The Lovász Local Lemma
18 (136) Theorems
of Euler and Rényi on 'e'
19 (140) A Theorem on Rectangular Tensegrities
20 (144) Lieb's Square Ice Theorem
21 (146) The Panarboreal Formula
22 (150) Woodall's Hopping Lemma
23 (155) A Tripartite Turán Theorem
24 (162) Heath's Finitely Discontinuous Function Theorem
25 (163) The Friendship Theorem |
