I don't know if [0] would be any help, it doesn't talk about graphs in particular but does talk about functional-focused approaches to data structures. This note[1] on the wikipedia page for the book says it better than I could:
> [...] consider a function that accepts a mutable list, removes the first element from the list, and returns that element. In a purely functional setting, removing an element from the list produces a new and shorter list, but does not update the original one. In order to be useful, therefore, a purely functional version of this function is likely to have to return the new list along with the removed element. In the most general case, a program converted in this way must return the "state" or "store" of the program as an additional result from every function call. Such a program is said to be written in store-passing style.
> [...] consider a function that accepts a mutable list, removes the first element from the list, and returns that element. In a purely functional setting, removing an element from the list produces a new and shorter list, but does not update the original one. In order to be useful, therefore, a purely functional version of this function is likely to have to return the new list along with the removed element. In the most general case, a program converted in this way must return the "state" or "store" of the program as an additional result from every function call. Such a program is said to be written in store-passing style.
[0] https://www.cs.cmu.edu/~rwh/students/okasaki.pdf
[1] https://en.wikipedia.org/wiki/Purely_functional_data_structu...