Systematic change of neighborhood within a possibly randomized local search algorithm yields a simple and effective metaheuristic for combinatorial and global optimization, called Variable Neighborhood Search (VNS). We present a basic scheme for this purpose which can easily be implemented using any local search algorithm as a subroutine. Its effectiveness is illustrated by solving several classical combinatorial optimization problems. Moreover, for solving large problem instances, the same basic scheme is used within the successive approximation method yielding a two-level VNS, called Variable Neighborhood Decomposition Search (VNDS). Finally, we discuss various ways to use VNS in graph theory, i.e. to suggest, disprove or give hints on how to prove conjectures, an area where metaheuristics do not appear to have been applied before.