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

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