IMO resources for Graph Theory

I will be participating as a trainer for Canada’s 2018 IMO Summer Training camp. I’m giving a session on graph theory. As I prepared my notes I found many resources online that already cover some aspects of graph theory. So here are those resources:

“IMO Training 2008: Graph Theory” by Adrian Tung.

This is an in-depth description of the basic combinatorial and geometric techniques in graph theory. It is a very thorough and helpful document with many Olympiad level problems for each topic. (No solutions are given.)

Topics include:

1. Trees and Balancing
2. Friends, Strangers and Cliques
3. Directed Graphs and Tournaments
4. Matchings
5. Hamiltonian/Eulerian Paths/Cycles

“Graph Theory” by Po-Shen Lo. (2008)

A large collection of problems and topics almost all of which have solutions or hints.

Topics include:

1. Basic facts
2. Extremal Graph Theory
3. Matchings
4. Ramsey Theory
5. Planarity

“Graph Theory” by Matthew Brennan. (Canada Winter Camp, 2014)

Contains a concise list of important results together with a guided discussion to five example problems that use graph theory.

“Probabilistic Method/Graph Theory” by James Rickards. (Canada Summer Camp, 2015)

An introduction to the probabilistic method in graph theory along with 10 problems.

“SIMO Graph Theory Training”. (SIMO training 2003)

A list of about 30 problems and solutions in graph theory.

Topics:

1. Graph Theory
2. Coloring problems

“Ramsey Theory and the IMO” by Ben Green. (2008)

This is a 4 page article that introduces Ramsey Theory for graphs and arithmetic progressions and its historical relation to the IMO.

“Coloring Points” at Cut-the-knot

A collection of 12 topics about coloring graphs and planes. There are many problems with solutions.

“Equivalence of seven major theorems in combinatorics” by Robert Borgersen (2004).

This series of slides states 7 results in extremal combinatorics that are really the same.

Topics:

1. Dilworth’s Theorem
2. Konig’s Bipartite Theorem
3. Hall’s Marriage Theorem
4. Menger’s Theorem
5. (Others)

One thought on “IMO resources for Graph Theory”

1. pgadey says:

Oooh! Nice round-up.

Thanks for posting all this!

Like