I like the idea of combining both a fixed set of test cases and running a couple of random tests next to that.

The idea behind the fixed set of test cases is to use a couple of very simple ones there (that you can easily reason about), along with edge cases (an empty graph, a single-node graph, one without edges, one (small) fully connected, etc.).
When you discover bugs that are only triggered by certain types of graphs (e.g., via the random test), you can try and add another test case in the fixed set that triggers that bug.
Adding comments for 'special' graphs to document why there were added is important too.

The current fixed set you added now is rubbish: the style is not acceptable (way too long lines, etc.), and it's possible that just one of these tests is just as valuable as all the others, so you're basically running the same test a bunch of times, without covering corner cases, 'special' graphs (I'm not sure if there are any in this context), etc.

If the problem with the updating of the dict was specific to a certain type of graph, try constructing a simple example if possible. If not, just include a fixed set as described above (empty, one node, etc.). If you can't easily minimalize a test case you ran into, then just add it as is (taking into account the code style guidelines w.r.t. long lines & indentation).

Then I feel it's OK to have another random test next to it; I really like that idea, and we should probably apply it to other unit test modules too, where applicable.
For logging: only test cases that fail are relevant imho, you don't need to keep a history across unit test suite runs (we have nothing like that in place, and there shouldn't be saved state across runs imho), so make sure they're printed properly in the error message if a test fails, preferably in a format you can copy-paste to then add to the fixed set (maybe after minimalizing it first).