Results 1 to 4 of 4

Math Help - Proof of being Eulerian

  1. #1
    Len
    Len is offline
    Member
    Joined
    Mar 2008
    Posts
    93
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by Len View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Len
    Len is offline
    Member
    Joined
    Mar 2008
    Posts
    93
    Thanks
    1
    Quote Originally Posted by Plato View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by Len View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Eulerian and hamiltonian questions
    Posted in the Discrete Math Forum
    Replies: 15
    Last Post: October 13th 2010, 07:03 AM
  2. Replies: 1
    Last Post: October 13th 2010, 03:58 AM
  3. [SOLVED] Eulerian graphs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 13th 2010, 10:40 AM
  4. Eulerian graph with even vertices and odd edges
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 23rd 2007, 03:12 PM
  5. eulerian graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2007, 03:41 AM

Search Tags


/mathhelpforum @mathhelpforum