On the rigidity of k-step nilpotent graph Lie algebras

We thoroughly explore the class of [Formula: see text]-step nilpotent Lie algebras associated with a simple graph looking for [Formula: see text]-step nilpotent Lie algebras which are rigid in the variety of at most [Formula: see text]-step nilpotent Lie algebras. We find out that, besides the complete graph, the only examples arise for [Formula: see text] and graphs of at most four vertices. A key tool to prove non-[Formula: see text]-rigidity, in this context, is a general construction of nontrivial deformations for naturally graded nilpotent Lie algebras.