We now turn our attention to Rule REF . Let \(G^{\prime }\)  denote the
graph obtained from the removal of \(|K|-(2k+2)\)  arbitrary vertices from \(K\) 
in \(G\)  and \(K^{\prime } = V(G) \setminus V(G^{\prime })\) .
Assume first that \(G\)  admits a \(k\) -edition \(F\) . Observe that
\(F\)  is a \(k\) -edition of \(G^{\prime }\)  by heredity. Conversely, assume that \(G^{\prime }\)  admits
a \(k\) -edition \(F\)  and let \(H^{\prime } = G^{\prime } \triangle F\) .
Notice that since \(F\)  affects at most \(2k\)  vertices and since
\(|K \setminus K^{\prime }| = 2k+2\) , there
exist two unaffected vertices \(u\)  and \(v\)  in \(K \setminus K^{\prime }\) .
We claim that \(H = G \triangle F^{\prime }\)  is a block graph. Assume for a contradiction that \(H\)  contains an obstruction \(W\) .
By construction, \(W\)  must intersect \(K^{\prime }\)  since otherwise \(W\)  would exist in \(H^{\prime }\) . Moreover, notice that
\(|W \cap K^{\prime }| \leqslant 2\) , otherwise \(W\)  would contain a clique module
with 3 or 4 vertices, which is impossible in a cycle or
a diamond. Hence assume first that \(|W \cap K^{\prime }| = \lbrace a\rbrace \) : in this case, since \(u\)  is unaffected we have \(N_{H}[a] = N_{H^{\prime }}[u]\)  and thus the
set \((W \setminus \lbrace a\rbrace ) \cup \lbrace u\rbrace \)  induces an obstruction in \(H^{\prime }\) , a contradiction. Similarly, if \(|W \cap K^{\prime }| = \lbrace a,b\rbrace \)  the set
\((W \setminus \lbrace a,b\rbrace ) \cup \lbrace u,v\rbrace \)  induces an obstruction in \(H^{\prime }\) , leading
once again to a contradiction.
Finally, since the biconnected components can be computed in \(O(n+m)\)  time [1]}, since block graphs can be recognized in \(O(n+m)\)  time and since true twins can be detected in \(O(n+m)\)  time (using modular decomposition [2]}), both rules can be computed in linear time.
