
Yes, I think you are right and here it is a proof: let's suppose the optimum solution is composed of vertices x_1, x_2, ..., x_k and let's suppose for the sake of contradiction that this solution can only be found at a step s > k + 1 (and contradict with your observation) then you must have that vertices 1, 2, ..., s  1 are part of the solution (the ones you tried so far), otherwise you would have been able to find this solution earlier. Thus, you must have k >= s  1 which implies k + 1 >= s, a contradiction.
Anyway this won't improve in the quadratic number of steps. Consider the case of a complete graph, in which you have an edge between every two vertices. 