Thread: Proof of being Eulerian

Let G be a simple connected regular graph that is not Eulerian.
Prove that if G' is connected then G' is Eulerian.

Hi, I'm having a difficult time starting these proofs, with a tip from the last one I was able to get going so I was wondering if someone could help get me started on this one.

I know that to be Eulerian G' must have a closed trail that includes every edge of G'

Thanks and + rep

Originally Posted by Len

Let G be a simple connected regular graph that is not Eulerian.
Prove that if G' is connected then G' is Eulerian.
I know that to be Eulerian G' must have a closed trail that includes every edge of G'

Also each of the vertices in G' must be of even degree.

Originally Posted by Plato

Also each of the vertices in G' must be of even degree.

I see that now, since we have a circuit, each time it visits a vertex, it does so twice, once in and once out.

Therefore G must have vertex of odd degree then.

How do I use this tho? I'm sorry

Originally Posted by Len

Therefore G must have vertex of odd degree then.
How do I use this tho?

We are given that the graph is connected, regular and non-Eulerian. So each vertex has the same odd degree. Moreover there must be an even number of vertices.This means the in G' each vertex is even.