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

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 \geq 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.