Given a graph $ G $ and its set of vertices $ V $. Taking into account the following problem:
there are two sets of separate vertices $ V_1 $ Y $ V_2 $ ( $ V_1 cup V_2 = V $) such that both $ V_1 $ Y $ V_2 $ they are covered with vertices of $ G $?
I wonder if the previous decision problem is difficult.
We can probably ask continuously "is there a vertex-size cover? $ k $ ($ k = 1,2, …, | V | $)? "Suppose we find an answer $ V_1 $ of size $ k $. Then we can check if $ V – V_1 $ It is a vertex cover. Does this argument show that the original decision problem is difficult?