We endow the set of all graphs G with a directed graph structure by inserting a directed edge (G, H) between two graphs G := (U, F ) ∈ G and H = (W, D) ∈ G if H is the result of a natural join of 2-cuts from G and one of the base elements B i ∈ B. Let us denote the resulting graph by ⃗ G. In Additional file 1 we show in a purely graphical manner that all local neighborhoods of a vertex of degree at most four can be interconverted by natural cut-and-join crossover with members of B. As an immediate consequence, we see that every graph can be stepwisely built up from the base set, and each of the construction steps is reversible by Lemma 3. This implies Theorem 4. The search space graph Ĝ is strongly connected.