How many vertices should we discard so that the remaining partial graph is Eulerian

Question

Let V be an undirected graph with 100 nodes and 4950 edges. How many edges should we delete so that the remaining partial graph is Eulerian ? And what's the reasoning ?

Answer 1

A simple graph on $100$ vertices has at most $\binom{100}{2} = 4950$ edges. So the graph in question is the complete graph on 100 vertices, $K_{100}$. Each vertex of $K_{100}$ has degree $99$, so $K_{100}$ is not Eulerian. If you delete $1$ vertex from $K_{100}$, you obtain $K_{99}$, each vertex of which has degree $98$, and thus is Eulerian. So $1$ vertex is both necessary and sufficient.

Edit: Now that you mean that you want to delete edges, not vertices, $K_{100}$ has $100$ vertices of odd degree. So we must delete at least $1$ edge incident with each vertex in order to make the graph Eulerian. Since each edge is incident with $2$ vertices, this means we must delete at least $50$ edges. If you delete perfect matching in $K_{100}$, all remaining vertices will have degree $98$, and will thus be Eulerian. So $50$ edges is both necessary and sufficient.