What is actually the right approach to solve the problem Testgen , how to figure out the failing of heuristics in the problem.
For the first two solutions, I just started looking for testcases which had a correct solution for only a single permutation of all edges. Which worked at 120 edges.
Best results had the strategy to connect all nodes to a single random node and add some more random edges to it. At the end i shuffled all edges again. This lead to a 79 pts solution. Only Solution3 did not work out. For 79 pts you need 100 edges or less. I figured out that 55-65 nodes and 100 edges often lead to good results for the Solution1,2 and 4.