Textbook or video lectures to develope intuition for solving any unseen Graph Theory problems

Question

Background

Hello, I am a third year undergraduate in CS. I am eager to pursue higher education from one of the best institutes in out country. For that I need to write a competitive exam, named GATE which had this syllabus for this year 2021. The syllabus remains more or less the same each and every year.

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 graph 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 on 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 counter examples for them to prove them wrong. At worse for some statements it might happen, that I am unable to find the counter example in that 2.76 mins of time, but it might happen that a more difficult counter example 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 or graph theory algorithms and properties of tree produced by traversals etc. But the thing is that all these I have learnt, by going through the text many times and I have been quite slow at grasping those concepts given in CLRS.I have even gone to Kenneth Rosen's Discrete Mathematics texts. As per the recommendations given in few coaching institutes (note that I do not go to any one of them, I do self study, got to know from my classmate), I have picked up Narsingh Deo's Graph Theory text and I am going through it now.

[I have solved most of the exercise questions of CLRS (except for the $\star$ questions) mostly on my own but only for once, long a 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 learnt...]

Could anyone recommend me some good text or detailed video lecture series (not a very advanced one) that would help me to build intuition behind graph theory properties or statements unknown to me. 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

I'm writing only a partial answer, because I currently lack time. That means that I'm not properly sourcing everything, and largely working from my own memory. I don't believe that anything I say below will be wrong, though it is definitely possible that I might be forgetting a few things. In any case, hopefully this will be enough to get you started / unstuck.

The test does look quite difficult! I teach several of the topics, and they were largely what I would expect from the end of an undergraduate university degree, but with the added pressure of timing and high stakes. Ouch!

When attempting to gain fluency (in any topic), you are looking to make a few kinds of connections:

1. "This is just like..." -- these connections allow you to utilize systems that your brain already understands well.

2. "These ideas group together" -- this is called "chunking", and it is how we group small ideas into larger and larger pictures. When you "chunk" ideas together, you are able to manipulate the chunk in your mind instead of all of the small details.

3. "This system looks like" -- much like #1, this allows you to "see" how systems work in your mind's eye. Then you can manipulate your visuals.

In essence, you are trying to group and simplify ideas.

To gain fluency, additionally, don't be afraid of memorization (though don't focus on it exclusively, either.) The purpose of memorization should not be to be able to regurgitate everything, but rather to give you quick enough recall that you can use the idea in a larger system.

Think about it this way: there is a cognitive tax to using any idea that we know. If the cognitive tax is very high, then using the idea takes nearly all of our focus. This limits what we can learn, because to really understand larger ideas, we need space in the active, working parts of our brain to encompass all of the smaller ideas that the larger idea needs. If the smaller ideas are taking up all of our active resources, that becomes impossible.

Thus, the goal of memorization is to reduce cognitive tax. If you are working hard to memorize beyond that, then you are wasting your efforts - you are not going to gain further fluency through memorization. You need to instead focus on chunking, visualizing, and relating ideas to one another so that you can see bigger pictures and larger groups.

Also, it is useful to practice on a mix of simple and hard problems. The first group reinforce and strengthen the patterned connections that you have already made. The second group force you to stretch those patterns out in new directions, and can help you spot new uses and simplifications.

I have always found that teaching others helps me to gain fluency, as it forces me to make explanations that distill systems for other people.

Good luck!