I would like to learn a bit of Graph theory for mathematical Olympiads.Can anyone please point out a resource from where I can learn it? Here's my background: I have limited knowledge of linear algebra but I know basic combinatorics including counting, pigeonhole principle, bijection, recursion, counting in two ways etc.I do not mind an elementary but really tough introductory book/resource.Thanks a lot in advance.
Graph theory resource for mathematical Olympiads
3 Answers
I'll post a host of three links:
See here for some problems in graph theory used by its author in engaging students preparing for IMO at the camp.
and here for some elementary notes in graph theory.
And, a book whose title suits your description is "Graph Theory for the Olympiad Enthusiast" published by South African Math Society. You must be knowing places where you can download books. I'll keep mum about this here.
Another thing I'll add is this book: "Pearls in Graph Theory: A Comprehensive Introduction". This is published by Academic Press. This is a wonderful book that touches to topics that are non-routine to beginners.
For a book length treatment, with practice problems that are challenging, I would highly recommend Douglas West, Introduction to Graph Theory (2nd edition), Prentice-Hall, 2001. However, for a very short but somewhat comprehensive introduction I would recommend the introductory chapter of Graph Connections (ed. Lowell Beineke and Robin Wison), Oxford, 1997. The first chapter by Robin Wilson is 13 pages long. Other chapters connect graphs to groups, geometry, number theory, topology, knots, linear algebra, etc. The exposition is top notch.
Part 3 of Discrete and Combinatorial Mathematics, An Applied Introduction by Ralph P.Grimaldi (4th editon): "Graph theory and applications".