Most of these examples are either naturally graphs already, or on the contrary, can be presented as graphs through ingenious reductions (e.g. coloring as an approach to register optimization). So transforming the domain problem to a graph theory problem is either trivial or hard.

I found that a huge benefit of knowing some graph theory lies in being able to approach problems where this transformation is easy - neither trivial nor hard, but easy once you have some experience and intuition working with graphs. Every time you have a bunch of entities, and you can kinda think of their interdependencies as a binary relationship of some sort, there's a warning bulb going off in your brain - "is this a graph problem?". And if it is, then very possibly you immediately get lots of insight into your problem, basically for free.

This occurred to me a few weeks ago as I was thinking about this puzzle: design a circuit that inverts three inputs, but uses only two NOT gates (plus arbitrary amount of ORs and ANDs). It's an interesting puzzle to solve manually, but I also wanted to quickly write a program to find the solution. Circuits are trivially graphs, but there're too many of them (an infinity) to iterate over. Once you see the problem as a reachability problem in a certain fixed graph, however (easy, but not trivial), the code writes itself. Someone with no exposure to graph theory might easily just balk at this easy problem, not knowing how to proceed.