Let $G$ be the graph obtained from $G_1 \cup G2$ by adding the edge $v_1v_2$ . Is $G$ Eulerian?

263 Views Asked by At

I'm currently working in the following graph-theory excercise:

Let $G_1$ and $G_2$ be two Eulerian graphs with no vertex in common. Let $v_1$ $V(G_1)$ and $v_2$ $V(G_2)$. Let $G$ be the graph obtained from $G_1 \cup G2$ by adding the edge $v_1v_2$ . What can be said about $G$?

My answer is that as $G_1$ and $G_2$ are Eulerian graphs then by Euler's theorem all of their vertex are even, but by adding the edge $v_1v_2$ then $v_1$ and $v_2$ are odd, then $G$ is a semi-eulerian graph. Is that correct? Thanks in advance for any critic or correction.

1

There are 1 best solutions below

0
On BEST ANSWER

Your proof seems fine.

Alternatively, you could be more direct if you wanted. You may use the new edge to get from $G_1$ to $G_2$, but you can't get back. So clearly $G$ can't be Eulerian. But you can find a path starting and ending in $v_1$ which walks all the edges of $G_1$, then you can go over the new edge, then walk all the edges of $G_2$. So $G$ is semi-Eulerian.