A constructive existence theorem related to local transformations of graphs for the independent set problem

For a given graph, the independent set problem is to find the size of a maximum set of pairwise non-adjacent its vertices. There are numerous cases of NP-hardness and polynomial-time solvability of this problem. To determine a computational status of the independent set problem, local transformations of graphs are often used. The paper considers some class of replacements of subgraphs in graphs that change the independence number in a controllable way. Every such local transform of a graph is determined by some pattern which is a subset of the power set. It is obvious that this pattern must be gradable. The paper shows that replacing subgraph exists for any gradable pattern.