Graph theory and algorithm engineering overlap a great deal. And not only in the directly graph theoretic terms like BFS, Dijkstra, Flow, etc, but also in that you need a good grasp of greedy algorithms, dynamic programming, divide and conquer, and several other general techniques.
Kind of like how being good at relational-databases and SQL is different than being good at coding up B-tree implementations.
The advice is sound -- if you want money focus on the flashy buzzword thing, not the actually useful thing.