1
$\begingroup$

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 easily. (While for a first timer, it might take days to understand a single precise proof, which might lead to hopelessness) 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.

$\endgroup$
2
  • 1
    $\begingroup$ It's dangerous to say that the graph theory textbooks are "proving something which only experts can understand". If you're not even planning to be able to understand these theorems, you're not planning to learn graph theory. $\endgroup$ Apr 22, 2021 at 15:00
  • $\begingroup$ Yes, I agree but if one is burdened with heavy notations, Greek symbols and other subtleties,then for a first timer who is learning the concepts (like me you who does not specifically know the intuition of matching, vertex covering, ...) for him learning no longer is a fun , it becomes something dangerous. On the other hand, reading these specific books (with intuition already developed) you shall enjoy how to tactfully write formal precise proofs, without long words of explanation. I am learning the concepts on my own (without any instructor), so these problems. I hope I could express myself. $\endgroup$ Apr 22, 2021 at 15:14

1 Answer 1

1
$\begingroup$

This syllabus doesn't appear to focus on graph theory heavily at all. You should be able to pick up the graph theory you need from a general discrete math textbook. If you want something that focuses on examples, intuition, and explanation, I recommend Discrete Mathematics: Elementary and Beyond by Lovász, Pelikán, and Vesztergombi.

If you do find yourself reading a more thorough textbook like West's Introduction to Graph Theory, I recommend changing your approach. This textbook covers a lot of material, and does actually give the intuition you're looking for, but you have to read and not just skim. In particular, having to read a proof multiple times to understand it is not a flaw in how the proof is presented; it is the way you should always read proofs. And you should write notes to yourself and draw diagrams as you read the proof!

Here is the syllabus for a class I taught based on this book; you can see that a single section of the textbook (10-15 pages) takes me one or two 50-minute lectures. If you are self-studying, you should not be reading the book much faster than this. Of course, some parts may go faster and some slower, and the exercises (which this estimate doesn't take into account) should be taking up a lot of your time as well.

$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.