Covering numbers of regular multigraphs (Q753843)

Let n be odd. For every n-regular multigraph G on N vertices \(\alpha_ 1(G)\leq \lfloor (2n-3)N/(3n-4)\rfloor\), where \(\alpha_ 1(G)\) is the minimum size of an edge cover (i.e. a family of edges such that every vertex is incident with some of them). On the other hand, if N is a multiple of \(3n+1\) then there exists a multigraph G with \(\alpha_ 1(G)=2nN/(3n+1)\).