That's exactly the trade off, isn't it? Either you do the work to store the relationships and save on the compute and memory cost later, or you pay as you go to build it in real time with a relational database. It's horses for courses.
It could be argued that a graph dB is just a really badly implemented index.
To propose a different perspective, a relationship in a graph db is like a materialized join. You pay on relationship creation (you might be using index lookups to find the nodes to connect, similar to a relational db), then for traversal it's just pointer hopping across the relationships to the connected nodes. Aside from the initial lookup of starting node(s), traversing the graph won't use indexes at all, so becomes constant time operations.