Characterization of graphs with given order, given size and given matching number that minimize nullity

Let G=(V(G),E(G))G=(V(G),E(G)) be a finite undirected graph without loops and multiple edges, c(G)=|E(G)|−|V(G)|+θ(G)c(G)=|E(G)|−|V(G)|+θ(G) be the dimension of cycle spaces of GG with θ(G)θ(G) the number of connected components of GG, m(G)m(G) be the matching number of GG, and η(G)η(G) be the nullity of GG. It was shown in Wang and Wong (2014) that the nullity η(G)η(G) of GG is bounded by an upper bound and a lower bound as |V(G)|−2m(G)−c(G)≤η(G)≤|V(G)|−2m(G)+2c(G).|V(G)|−2m(G)−c(G)≤η(G)≤|V(G)|−2m(G)+2c(G). Graphs with nullity attaining the upper bound have been characterized by Song et al. (2015). However, the problem of characterization of graphs whose nullity attain the lower bound is left open till now.In this paper, we are devoted to solve this open problem, proving that η(G)=|V(G)|−2m(G)−c(G)η(G)=|V(G)|−2m(G)−c(G) if and only if the cycles (if any) of GG are pairwise vertex-disjoint and GG can be switched, by a series of operations of deleting a pendant vertex together with its adjacent vertex, to an induced subgraph of GG, which is the disjoint union of c(G)c(G) odd cycles and |V(G)|−2m(G)−c(G)|V(G)|−2m(G)−c(G) isolated vertices.