As already mentioned, the connectivity property of neutral networks of RNA structures has a profound impact on our picture of evolutionary optimization. It is closely related to the connectivity of the two subcubes induced by the unpaired and paired nucleotides. We present the combinatorial, constructive proof that localizes the threshold value for generalized n-cubes due to . The particular construction has led to several computational studies on the connectivity of neutral networks [11, 12].
Lemma 5.1 Let Qnα be a generalized n-cube, , and Γ n an induced Qnα-subgraph obtained by selecting each Qnα-vertex with independent probability λ. Then we have
Proof. Claim1. Suppose . Then for arbitrary l∈,Γn contains a.s. exclusively vertices of degree ≥ l.
To prove the claim we first observe that is equivalent to (1–λ)α–1)α<1. We fix l ∈ . Using the linearity of expectation, ...