Very good question, but very tough to answer. I highly doubt, that such a book exists, because graphs are just another formalism and whether you apply it to your problem or not is a matter of two things:

1. Knowledge about its existence. People who do not know about graphs and the corresponding algorithms for some very strange reason never come up with graph-based solutions to their problems.

2. Being the most suitable formalism for your problem.

As for 1. you are well on your way already. Point 2 is much harder due to the genericity of graphs. If you take it to the extreme, do remember that every list or array is nothing but a graph in disguise. Now you could consider looping through a linked list in order to find a certain element as a depth-first search on a directed acyclic graph, but there’s really no point in it apart from the mental masturbation.

On the other hand, there are myriads of problems which naturally lend themselves to graph-based solutions. The more experience you have with graphs, the more you will see them wherever you go, but it takes even more experience to decide when the time is right to pull out that full-blown graph library, or even roll your own algorithm.

If you are looking for a problem that requires a graph-based solution, then my guess is you won’t find one, as it all could be solved in a different way as well. But if you’re looking for problems for which graph-based solutions are a good fit, then your best bet might be to look at an abstraction of the problem.

Abstraction is the one thing that brings out graph datastructures the best. Try to translate your problem domain into nodes and figure out what the meaning of an edge between these nodes would be. If you cannot do that easily, chances are you are better off without graphs. However, most of the times everything just falls into place naturally.

Here are a few examples and how abstraction leads you to the corresponding graph algorithms:

• Buildsystem: you have a lot of projects/libraries which depend on each other. You must ensure that one is built before another, oh and of course, if possible, you want to build them in parallel. Now do the abstraction: library = node and edge = dependency and voila.. you have a graph. Next question: what structure does this graph have? is it directed or undirected? has to be directed, as you have a direct relation that one library needs to be built before the other. Is it acyclic? indeed, you cannot have cyclic dependencies, or you would not have a place to start your build – but you may have to account for your tool being able to stop on detecting cycles, because someone configured something wrong. Ops, cycle-detection algorithm.. should be in your toolbox. Next up: determine the execution order for builds, or in other words: find a traversal through your graph that visits nodes only after all nodes from incoming edges have been visited. Check your toolbox, as this is the topological sort algorithm. And so on, and so on…

• Power net: You have a city/country and several power plants and places where you can redirect power and of course, everyone needs to be supplied. Nodes are the homes and power plants, edges are the power lines, and if you want to find the minimal length of power lines you need to build, it comes down to the minimal amount of edges required to connect all of your nodes together.. or in toolbox-speech: minimum spanning tree.

• Piping system: You have an elaborate setup of pipes through which you can run water. At several points you have the option to open/close valves to allow the water to pass through your system in different ways. However, the pipes differ in diameter, so that the throughput varies and you wonder: how much water can we get pumped through this system at most (in a given unit of time)? Abstraction leads you to model the tap, sink, and valves as nodes and pipes as edges. Edge weights will be involved due to the diameters affecting the throughput and now you want to find quite literally the maximum flow. Luckily, the graph toolbox has algorithms for just that.

• Routing wires on a chip (example proposed by @jk.) : When you have to do wiring, you have the limitation, that wires must not cross due to the electrical charges. Abstraction is straight-forward at first, because you have components and wires between them, hence, nodes and edges. The next step is to identify the problem in graph-based terms, which in this case means you have to layout the edges on a plane. Whether or not a graph can be drawn on a plane without intersecting the edges is again checkable via an algorithm from the graph toolbox – keyword: planar graphs.

As for the spoon-feeding book: This is actually not a good idea. Let me stress again, that graphs can be applied to almost every problem if you force your mind around it. A book that shows you problems and how they are solved with graph algorithms is pretty much useless, because you will have to deal with other problems in your daily work. All it comes down to is experience with this kind of abstraction, because you have to adapt everything to the current situation at hand.