In a graph, an edge dominating set is a subset D of the edges such that any edge in the graph is either in D, or shares an endpoint with an edge in D. The Minimum Edge Dominating Set problem is to find an edge dominating set of minimum cardinality. The decision version of this problem is known to be NP-complete, but I would like to inquire whether a relatively simple proof of this fact is known.
The only proof I found in the literature is in the paper that first tackled this problem, by Gavril and Yannakakis. However, the above proof makes use of the fact that Vertex Cover is NP-complete for planar cubic graphs, and the fact that bipartite graphs of degree d can be d-edge-colored. I would prefer a simpler proof, that would only make use of facts typically known to undergraduates who took an algorithms course.