Minimum order of a graph with given deficiency and either minimum or maximum degree (Q2713648)

A matching of a graph \(G\) is a subset of its edge set such that no two edges of this set have a common end vertex. A matching of \(G\) with the maximum number of edges is called a maximum matching of \(G\). If \(M\) is a maximum matching of \(G\), then the number of vertices of \(G\) incident to no edge of \(M\) is called the deficiency def\((G)\) of \(G\). In the paper lower bounds for the number of vertices of a graph with given deficiency and given minimum degree and with given deficiency and given maximum degree are found.