In this paper, the first steps toward the use of the Variable Neighborhood Search metaheuristic are explained. The method is presented step by step using an example taken from the search for extremal graphs that was used at in the early stage of the AutoGraphiX software (https://www.gerad.ca/Gilles.Caporossi/agx/AGX). Some extensions are also briefly described.