Computational complexity of graph extensions

A graph $G^*$ is $k$-vertex (edge) extension of graph $G$ if every graph obtained by removing any $k$ vertexes (edges) from $G^*$ contains $G$. We prove NP-completeness of the problem: "Is graph $G^*$ a $k$-vertex (edge) extension of graph $G$?".