# Proof of being Eulerian

• Feb 12th 2011, 12:54 PM
Len
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
• Feb 12th 2011, 01:26 PM
Plato
Quote:

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.
• Feb 12th 2011, 10:15 PM
Len
Quote:

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
• Feb 13th 2011, 02:40 AM
Plato
Quote:

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.