An intuitive (non rigorous) text book on graph theory which is student friendly with vivid illustrations

Question

Background

Hello, I am an undergraduate in CS. I would like to study Graph Theory on my own (self-study) for a competitive examination (named GATE). It is an examination for undergraduates and as such, I would like to concentrate on the topics which are there normally in a standard UG graph theory course. The syllabus for the examination.

The pattern is as follows, 65 questions, time 3 hours. So for each question, I can afford at most 2.76 mins, which is quite a constrained amount of time, considering the level of the questions.

This is to give an idea about the level of the questions

---

Problem

As per the given syllabus, the exam asks quite involving questions on Graph Theory, with questions based on properties of the graph after applying certain algorithms, tree formed by traversals, or coloring, or other important but at times unseen (by the candidates) properties or concepts. Mostly they tend to ask questions from unseen topics, which probably one has not handled previously unless he is quite lucky. In such cases, they definite the topics and then asks about them.

Usually, questions are like select the most appropriate options or marking the true statements.

Now it is quite difficult (for me at least) to understand in 2.76 mins the new concept (defined in the question), read the statements, find counterexamples for them to prove them wrong. At worse for some statements, I might be unable to find the counterexample in that 2.76 mins, but a more difficult counterexample might exist.

One can have a look at the type of question in graph theory here and here and here.

---

Situation/Request

I have gone through CLRS and I am acquainted with the terminologies of graph theory algorithms and properties of trees produced by traversals, etc. But the thing is that all these I have learned, by going through the text many times and I have been quite slow at grasping those concepts given in CLRS. I have even gone through Kenneth Rosen's Discrete Mathematics texts.

[I have solved most of the exercise questions of CLRS (except for the $\star$ questions) mostly on my own but only for once, long ago, while reading the text for the first time. Some questions even took a single day to think (too slow indeed). Rosen has a huge no of questions at the end of each text, that too I have solved not all but selectively as I found few problems repetitive there, and that too I have done only once. But I have read the text many more times (that too selectively) so that I do not forget the things which I have learned...]

Could anyone recommend me some good text that would help me to build intuition behind graph theory properties or statements unknown to me. A text which does not explain the concept with rigorous mathematical proofs. [I tried to read Douglas West's book, but it was so rigorous, that after completing the proof, one has to go through it once again to see, what he was actually proving]. I would like to read a text which is easy and explains the concepts using intuition and examples and logical reasoning, rather than going into rigorous mathematical proofs, assuming dangerous notational conventions, with 100s of greek symbols, and then proving something, which only experts can probably understand. I hope can express myself clearly. A text with many examples/illustrations of how every theorem which it states could be applied to problems. Probably one that also includes properties of trees and graphs, after some algorithms are applied to it, like, questions about articulation point in a DFS tree, properties of cross-edges, back-edges, etc.

The texts which I have already read are classic and fine, but I find it difficult at times to answer questions in the GATE, (might be due to the short time or might be that I am not that sharp) but still I want to sharpen my skills in dealing with these problems of graph theory. Even the weightage of this subject is quite high every year.

Thank you.

Answer 1

That book gets ripped pretty hard on Amazon. The Dover texts by Trudeau and Chartrand are supposedly easier and friendlier, per reviews. And will be cheap, since Dover.

If you want to develop familiarity and speed, I would certainly not eschew (i.e. I would do) problems that are repetitive. You'll get more practiced at the concept. Also more practiced at speed itself. You are a sharp fellow and this is an optimization problem. But if you're struggling with speed/familiarity/recall, I think more problems is a better answer than multiple rereadings (that is unusual...I find that I master a text, than can use it as a desk reference...very easily since it is "mastered"...if I really need super speed/skill again, it's best developed by selective drill...but that is a refresher from having done all the problems long ago).

Here is a "for dummies" article:

https://www.freecodecamp.org/news/i-dont-understand-graph-theory-1c96572a1401/

Now, I realize you are pretty sharp and knowledgeable given the work on the West book so far. Still, maybe this helps to get back to more pictorial intuition. It also has a bit more of a CS/industry slant, so perhaps that motivates you to remember concepts. Humans are not silicon-based math logic systems, we are overtrained hunter/gatherers. We remember things better with "import" and with multiple frames of reference, e.g. applied and theory both, pictorial and algebraic, etc.

P.s. I'm not a math theory graph expert or student at all--just little bit in practical scheduling/PM work. Essentially I just Googled for stuff that might help you. And applied some critical thinking, looking at textbook prefaces and the like. I know Amazon reviews are not perfect, but suggest looking at them. Also at prefaces and even skimming texts themselves before investing in deep effort. Of course at some point you have to jump in. But be wary of single point advice on texts. Especially on SE and from professors there can be a tendency to advise the books that are hardest versus most pedagogically effective. Or to ignore the questioner's stipulations, like telling someone who is a weak student to self study Rudin. (I sort of did too in your case...because the links were "hard" for me, but at least I knew I did..and I did click them at least...kudos for the detail by the way!) Also, for some reason Reddit is often more reasonable, helpful.