# Problem solving approaches in graph theory

From my experience with problems in graph theory, these pose certain obstacles that to me seem to particular for discrete mathematics, among them are

1) A solution might be obvious at first sight, but extremely hard to rigorously formulate/proof.

2) A problem statement is very hard to grasp, such that I don't even know how to start.

3) I rarely see a measure of "progress towards a solution"; either I get nowhere or I know from the beginning how to solve a problem/what theorem to use

4) Most problems seem to be "individual" in a sense that I can't identify a general concept that might be helpful for a problem that I will face in the future. In particular that means that finding too strong hints or even full solutions does not help at all. In other fields of math, even copying a well worked out solution might help, since it elucidates in what setting one can properly use a theorem/approach.

Do you have any recommendations of how to figure out conceptual elements in graph theory problem solving, i.e. how to figure out a setting and a general strategy that might be applicable to a certain style of problems?

Are there any good reads in graph theory that point out problem solving strategies/ways of thinking, instead of focusing on results?

-
How about the universal strategy of solving special cases first, and then generalizing? –  Shahab May 27 '13 at 13:31
Considering small examples (why a statement is true for all graphs with at most 4 vertices, for example) is usually a good starting point to build intuition about a problem. –  Samuel May 27 '13 at 13:32

As an experienced problem solver I allow myself to highly recommend to you a book “Mathematical discovery: on understanding, learning and teaching” by George Polya. In this book the author sketches the bases of a general method of mathematical problem solving. In graph theory it works too.

Also I can tell you that when your graph intuition will be developed highly enough, sometimes you will ‘see’ the answers. The checking and the proving of them is a technical task. This is why I regularly starts my answers at MSE with the sentence “It seems the following”. :-)

A couple of words about you partial obstacles.

1) You should be sufficiently skilled in techniques, not only in the intuitive vision.

2) Try to see a problem from different points of view, search familiar elements in the problem. Come up to the problem time after time. Gradually your vision of the problem will become clear.

3) This vision of “a measure of "progress towards a solution"” is a mysterious thing for me. Polya claims that such a feeling exists, but it seems that I does not hove it . Of course, when you have a program or a plan of the solution process (see the respective chapter of “Mathematical discovery” for more details) then after the realization of the phases of the plan you are able to estimate the progress, but this is a quite ideal case.

4) This obstacle is related with the experience. I think that thousands of mathematical problems which I solved or saw the solutions, formed my intuition.

-

Let $M$ be the incidence matrix and $A$ the Adjacency matrix of a graph $G$.

a. Show that every column sum of $M$ is $2$.

b. What are the column sums of $A$?

-