What are some of the best books on graph theory, particularly directed towards an upper division undergraduate student who has taken most the standard undergraduate courses? I'm learning graph theory as part of a combinatorics course, and would like to look deeper into it on my own. Thank you.
16 Answers
$\begingroup$
$\endgroup$
0
Try Bondy and Murty, Graph Theory. The previous version, Graph Theory with Applications, is available online.
$\begingroup$
$\endgroup$
3
Diestel's Graph Theory (which has a "free preview" online) is presented as a graduate textbook, but it does not really have any prerequisites.
It goes quite deep in some parts, and includes material (such as the chapter on the graph minor theorem) that you won't find in other textbooks. Some proofs have a sort of "how would someone ever think of that?" feel, but this may have been remedied in the fourth edition (I have the third).
-
1$\begingroup$ That's "Diestel". It may be noteworthy that this book has a German version, entitled without much originality "Graphentheorie". It's certainly the best introductory text for someone interested in the most theoretic aspects of graph theory. $\endgroup$ Commented Apr 5, 2011 at 20:56
-
$\begingroup$ @PseudoNeo Ah, usually I don't make that typo, thanks. $\endgroup$ Commented Apr 5, 2011 at 22:32
-
$\begingroup$ I have both Diestel and Bondy & Murty – I think Diestel is the clearer and more approachable of the two books, but Bondy and Murty is good too. $\endgroup$ Commented Mar 23, 2017 at 4:12
$\begingroup$
$\endgroup$
2
Doug West, Introduction to Graph Theory. Rigorous but readable, proof based rather than simply descriptive, but the proofs are explanatory rather than simply justification of truth (by any arbitrary means). Even so may not be the best total beginner's book.
-
4$\begingroup$ This is generally agreed by graph theorists to be the most readable yet comprehensive of the currently used textbooks.It IS rather expensive,though,so be warned. $\endgroup$ Commented Mar 10, 2015 at 4:57
-
1$\begingroup$ I have taught graph theory from Doug West's textbook; what I always tell students is that it is good, but must be read slowly and thoughtfully. A single page in the book can correspond to 5-10 minutes of class; you can read all the words in 1-2 minutes, but you will not understand them if you do. $\endgroup$ Commented Apr 1, 2022 at 3:42
$\begingroup$
$\endgroup$
2
I learned graph theory from the inexpensive duo of Introduction to Graph Theory by Richard J. Trudeau and Pearls in Graph Theory: A Comprehensive Introduction by Nora Hartsfield and Gerhard Ringel. Both are excellent despite their age and cover all the basics. They aren't the most comprehensive of sources and they do have some age issues if you want an up to date presentation, but for the basics they can't be beat.
There are lots of good recommendations here, but if cost isn't an issue, the most comprehensive text on the subject to date is Graph Theory And Its Applications by Jonathan Gross and Jay Yellen. This massive, beautifully written and illustrated tome covers just about everything you could possibly want to know about graph theory, including applications to computer science and combinatorics, as well as the best short introduction to topological graph theory you'll find anywhere. If you can afford it, I would heartily recommend it. Seriously.
-
$\begingroup$ I recently discovered Trudeau and was briefly considering making it the official textbook for the class I am teaching. It has a lot of really good parts: for example, there is a very good discussion of Kuratowski's theorem that actually goes into detail with an example of how to use it, in a way I've never seen any other textbook do. Unfortunately it is lacking in other areas: the discussion of complexity theory after Hamiltonian paths are introduced meanders between "actually false claims" and "too vague to tell". $\endgroup$ Commented Apr 1, 2022 at 3:39
-
1$\begingroup$ (These are just examples; I guess my main point is that its conversational style makes some topics very accessible, but also means that the depth suffers.) $\endgroup$ Commented Apr 1, 2022 at 3:47
$\begingroup$
$\endgroup$
1
The best introduction I could recommend for truly beginners is not a whole book on graph theory but A Walk Through Combinatorics, from Miklos Bona it has a large part of the book devoted to graph theory, from the very basics up to some intro to Ramsey theory
-
$\begingroup$ It even has a section on the matrix tree theorem, something one doesn't find often in introductory books $\endgroup$ Commented Jul 11, 2020 at 11:09
$\begingroup$
$\endgroup$
1
Pearls in Graph Theory: A Comprehensive Introduction by Nora Hartsfield and Gerhard Ringel.
I used this book to teach a course this semester, the students liked it and it is a very good book indeed. The book includes number of quasiindependent topics; each introduce a brach of graph theory. It avoids tecchnicalities at all costs. I would include in the book basic results in algebraic graph theory, say Kirchhoff's theorem, I would expand the chapter on algorithms, but the book is VERY GOOD anyway.
-
$\begingroup$ +1 for one of the wonderful inexpensive Dover books I used to learn graph theory. The other was Trudeu's wonderful book. $\endgroup$ Commented Mar 10, 2015 at 4:55
$\begingroup$
$\endgroup$
I enjoyed Alan Tucker's Applied Combinatorics. It's split into two sections:
- Graph Theory
- Combinatorics
The first half covers things like coloring theorems, cycles, and all that stuff. The second half is all about generating functions, counting sets, etc.
I found the book to be pretty readable. There are a lot of problems to work, which was nice.
$\begingroup$
$\endgroup$
I like Bollobás's Modern Graph Theory in the Springer GTM series. It is a bit dense, but worth chewing on.
$\begingroup$
$\endgroup$
You might find Graph Algorithms / Shimon Even interesting. Although it might probably hard to obtain.
Edit: You can get some of the chapters here.
$\begingroup$
$\endgroup$
2
Graph and Digraphs, 5th edition, by Chartrand, Lesniak, and Zhang. It is a graduate level text and gives a good introduction to many different topics in graph theory.
-
$\begingroup$ I don't think it's graduate level,but it's definitely harder slogging then the other books recommended here so far. A very good one though. $\endgroup$ Commented Mar 10, 2015 at 4:56
-
2$\begingroup$ Well, I took my graduate level graph theory classes as a student of Zhang using her book. By the time I had taken my qualifier in graph theory, I had worked damn near every problem in that book and it wasn't that easy. But for extremal graphs and random graphs, I spent a lot of time with Diestel. $\endgroup$ Commented Mar 10, 2015 at 5:24
$\begingroup$
$\endgroup$
I've enjoyed Introduction to Graph Theory by Wilson. Older version can be obtained for less than $5.
$\begingroup$
$\endgroup$
Here is Vadim Lozin's graph theory course. (Available for free from university of Warwick website )
It starts from scratch and most of theorems are prooved. I think it's pretty clear with many content.
It's not a book, but i hope it can help you.
$\begingroup$
$\endgroup$
1
Graph Theory: Modeling, Applications, and Algorithms by Geir Agnarsson and Raymond Greenlaw is a really good book. see this discussion for reference.
-
$\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. $\endgroup$– Shaun ♦Commented Oct 4, 2014 at 12:17