Generating networks that satisfy a given set of constraints can be very challenging, especially when the metrics being controlled for are not very prescriptive and the networks could potentially exhibit very different higher-order structure within those constraints. Network-generating algorithms typically produce fairly contrived networks and lack mechanisms by which to systematically sample the space of network solutions. In this paper, we explore the potential of a multi-objective novelty-biased GA to provide a viable alternative to these algorithms. We believe our results provide the first proof of principle that (i) it is possible to use GAs to generate graphs satisfying set levels of key classical graph theoretic properties and (ii) it is possible to generate diverse solutions within these constraints.