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

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!

• You're in the right direction, but the current proof is still missing a lot: 1) You start by supposing $u$ and $v$ have odd degree. You haven't said anything about what to do if one of them has even degree. 2) You claim there are no vertices of odd degree, but this is unjustified since you've only looked at $u,v,w$ and none of the other vertices in $V$. 3) Minor point: you should explain why the new graph is connected (in particular, why does the construction fail if $G$ is already Eulerian?) Nov 29, 2016 at 5:25

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.