In fact I think often when people recommend graph theory for computer science, they're thinking more about order theory (trees, DAGs, posets etc), or failing that, more the "basic algorithms over graphs" stuff than the "let's prove a bunch of clever theorems about k-colourings" kind of graph theory which you might get if you bought a book on it.
I take issue with the "actually useful" part. Had we been early 20th century citizens, you might have said that about number theory, but where would modern cryptography be without it?
And to clarify, there is nothing wrong with non useful Math.
You mean: there is nothing wrong with not yet useful Math. Math is always useful for finding Truth, and only sometimes useful when scientists find phenomena which can be described by it.