Only one graph of order 5 has the property that the addition of any edge produces an Eulerian graph. What is it?

Question

This is a homework question. However, I don't think that such a graph exists. Here's my attempt at proving that (I know I'm wrong; please tell me where I went wrong!):

For contradiction, assume such a graph G exists. Assume the vertices are called a, b, c, d, and e. Since the addition of any edge produces an Eulerian graph, adding the edge ab would do so. In order for a graph to be Eulerian, all its vertices must be of even degree. So now a, b, c, d, and e are of even degree. But that meant that beforehand, a and b were of odd degree, since adding one edge between two vertices changes their parity. So G has vertices a and b of odd degree, and c, d, and e of even degree. (*)

Since the addition of any edge produces an Eulerian graph, adding the edge cd would also do so. In order for a graph to be Eulerian, all its vertices must be of even degree. So now a, b, c, d, and e are of even degree. But that meant that beforehand, c and d were of odd degree, since adding one edge between two vertices changes their parity. So G has vertices c and d of odd degree, and a, b, and e of even degree. (**)

So (*) and (**) make a contradiction!

Where am I going wrong in this proof? I know I must be wrong because I have to find an example of such a graph (you could be finicky and say that some the vertices could be of degree 0, but it's still going to be a problem)

Answer 1

The intended answer is probably $K_5 - e$: the complete graph of order $5$, with a single edge removed. The only way to add an edge to this graph is to add the unique missing edge, which results in the Eulerian graph $K_5$.

There are two quibbles with this:

• If we consider multigraphs, rather than simple graphs, we could add an edge that's already present. In that case, it's possible to add a new copy of an existing edge to $K_5 - e$, and create a non-Eulerian multigraph. When considering multigraphs, the body of the question is a proof that there can be no solution.
• If we consider simple graphs only, so we specifically rephrase the property as "the addition of any edge not already present in the graph produces an Eulerian graph", then there is a second solution: the newly-rephrased property is vacuously true of $K_5$ itself, because there is no possible edge we can add.

I imagine that the question was intended to be about simple graphs only, and the vacuously-true answer of $K_5$ was overlooked by the author of the problem.

(This is an old question that mostly got resolved in the comments; I'm providing an answer for completeness.)