4
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ 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?) $\endgroup$
    – Erick Wong
    Nov 29, 2016 at 5:25

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Also, the new graph is connected, because the new vertex is connected to at least one old vertex (it's here that we use the requirement that the original graph was non-Eulerian). $\endgroup$ Nov 29, 2016 at 6:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .