The fixed set of test cases you include now are rubbish, it's very likely you're basically running the same test over and over again, and it's impossible to debug with test cases this huge.

Your fixed set of example graphs to test on should include a couple of edges cases (e.g. empty, one node, no edges, small yet fully connected, etc.), along with a couple of special cases that you've seen the code fail on (or of which you know they tickle certain corners in the code).
You can add random tests on top of that, I do like that idea. If one of those fails, you can then make sure to print the used graph, so it can be included in the fixed set of tests (hopefully after trimming it down to the essentials first). You don't need to log all test cases you've ever used imho, that's useless. Only the ones failing at some point are interesting, so you can deduce a (minimal) test case in the fixed set from them.