You should comment your code
I tend to prefer explicit type annotations and unit tests (later) over comments except when I feel like there's something non-intuitive that's not at all obvious from the code. Comments are also critical for future-safety against "fixes" that "look right" but will actually break the code.
I tend to have a "60-second rule". If it took 60 seconds for me to figure this out, then I should comment. For example, I commented the need for a curried function signature in Utils.mergeMaps because it wasn't at all obvious, and I kept getting type errors till I got it right.
Personally, I think the worst thing about what I have right now is that it really deserves to be split into more than one file, but I'm delaying the build system question (I dislike Maven, SBT seems neat has a bad reputation) for a little white.
Tests are a great way to show what your library can do. I recommend adding those before you worry about documentation. (How do you know your code, as posted, works?)
One thing I have to decide on this project is whether I'm going to follow the convention (which I don't like) of putting "test/" in a separate directory from "main/". I dislike it because I think unit tests should be included inline if short and relevant to the purpose of the function.
Generally, my testing practice is to REPL-test and then include the tests in code for posterity. It makes the testing process more playful to start in REPL testing. I know it's the opposite of TDD but it works for me.
And since you're writing a graph library, there definitely should be a detailed commentary on the implementation of the graph (e.g. representation of the graph structure, memory complexity of the representation, and time complexity of common operations). Once you start working with larger graphs, using the correct representation and algorithms for your task makes a huge difference and it is something that must not be hidden from the users.