Edge-deletable IM-extendable graphs with minimum number of edges

A graph GG is induced matching extendable, shortly IM-extendable, if every induced matching of GG is included in a perfect matching of GG. For a nonnegative integer kk, a graph GG is called a kk-edge-deletable IM-extendable graph, if, for every F⊆E(G)F⊆E(G) with |F|=k|F|=k, G−FG−F is IM-extendable. In this paper, we characterize the kk-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer kk, if GG is akk-edge-deletable IM-extendable graph on 2n2n vertices, then |E(G)|≥(k+2)n|E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅Kk+2,k+2G≅Kk+2,k+2, or k=4r−2k=4r−2 for some integer r≥3r≥3 and G≅C5[N2r]G≅C5[N2r], where N2rN2r is the empty graph on 2r2r vertices and C5[N2r]C5[N2r] is the graph obtained from C5C5 by replacing each vertex with a graph isomorphic to N2rN2r.