Minimum Number of Bridges on Connected Almost Cubic Graphs with Given Deficiency

Abstract

Let $G$ be a simple graph having a maximum matching $M$. The deficiency $\text{def}(G)$ of $G$ is the number of vertices unsaturated by $M$. A bridge in a connected graph $G$ is an edge $e$ of $G$ such that $G-e$ is disconnected. A graph is said to be almost cubic (or almost 3-regular) if one of its vertices has degree $3+e$, $e\ge 0$, and the others have degree 3. In this paper, we find the minimum number of bridges of connected almost cubic graphs with a given deficiency.