Minimum Order of a Graph with Given Deficiency and Either Minimum or Maximum Degree

Abstract

Let $G$ be a simple graph of order $n$ having a maximum matching $M$. The deficiency $def(G)$ of $G$ is the number of vertices unsaturated by $M$. In this paper, we find lower bounds for $n$ when $def(G)$ and the minimum degree (or maximum degree) of vertices are given. Further, for every $n$ not less than the bound and of the same parity as $def(G)$, there exists a graph $G$ with the given deficiency and minimum (maximum) degree.