Minimum Number of Vertices of Graphs without Perfect Matching, with Given Edge Connectivity and Minimum and Maximum Degrees

Abstract

A matching $M$ in a graph $G$ is a subset of $E(G)$ in which no two edges have a vertex in common. A vertex $V$ is unsaturated by $M$ if there is no edge of $M$ incident with $V$. A matching $M$ is called a perfect matching if there is no vertex of the graph that is unsaturated by $M$. Let $G$ be a $k$-edge-connected graph, $k\ge 1$, on even $n$ vertices, with minimum degree $r$ and maximum degree $r+e$, $e\ge 1$. In this paper, we find a lower bound for $n$ when $G$ has no perfect matchings.