MINIMUM NUMBER OF VERTICES OF ALMOST 3‑REGULAR GRAPHS WITH GIVEN DEFICIENCY
Let Gbe a simple graph having a maximum matching M. The deficiency of Gis the number of vertices unsaturated by M. In this paper, we find a lower bound for nwhen Gis a connected graph on nvertices, of which have degree 3 and one has degree and is given. Further, for every nnot less than the bound and of the same parity as there exists a connected graph Gon nvertices, of which have degree 3 and one has degree with given deficiency
number of vertices, almost 3-regular graph, deficiency.