Add a vertex to G so that the new graph is Eulerian

Question

The question says, "Let $G = (V, E)$ be a connected graph that is not Eulerian. Prove that it is possible to add a single vertex to $G$, together with some edges from the new vertex to some old vertices of $G$ so that the new graph is Eulerian."

So far what I've got for my answer is the following, and I want to see if I'm heading in the right direction:

"Let $u, v \in V$. $u$ is connected to $v $. This means that there is a $(u, v)$-path in $G$. Suppose $d(u)$ and $d(v)$ are odd. Let us add a vertex to $V$; namely, $w$. Let us also add some edges incident to $w$ and the vertices of odd degree. Now, $d(u)$ and $d(v)$ are even. $d(w) = 2$, so $d (w)$ is even as well. $\forall v \in V, d(v)$ is even. There are no vertices of odd degree, so $G$ is now Eulerian."

Any help would be appreciated!

Answer 1

More succinctly, you are adding a new vertex $w$, and connecting it to all vertices of the original graph that had odd degree. This makes all the original vertices have even degree, but we need to check the degree of $w$.

The degree of $w$ is the number of odd-degree vertices in the original graph, which is also even (consider the total degree of the original graph). In particular, the degree of $w$ is not necessarily $2$; I am not sure why you only considered two odd-degree vertices.

Finally, as others have pointed out, the degree of $w$ is not zero else the original graph would already have been Eulerian.

Answer 2

Using handshake lemma, the number of vertices with odd degree in a graph is even. So, add an edge from this new vertex to every vertex with odd degree in the previous graph thereby making the degree of all the vertices even.
And now using the characterization of Eulerian Graphs, the new graph is Eulerian.
As @darji rightly said, the new graph is connected because the new added vertex is connected to at least one vertex, and as the original graph was connected(didn't have any isolated vertex), the new graph is also connected.