Summary: \(K\)-best enumeration, which asks to output \(k\)-best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, \(k\)-best enumeration tends to be intractable since, in many cases, finding one optimum solution is NP-hard. To overcome this difficulty, we combine \(k\)-best enumeration with a concept of enumeration algorithms called approximation enumeration algorithms. As a main result, we propose a 4-approximation algorithm for minimal connected edge dominating sets which outputs \(k\) minimal solutions with cardinality at most \(4 \cdot \overline{\mathrm{OPT}}\), where \(\overline{\mathrm{OPT}}\) is the cardinality of a minimum solution which is not outputted by the algorithm. Our proposed algorithm runs in \(O(nm^2 \Delta)\) delay, where \(n, m, \Delta\) are the number of vertices, the number of edges, and the maximum degree of an input graph.