Results 1 to 7 of 7

Thread: Graph theory - Euler or not

  1. #1
    Newbie
    Joined
    Jun 2017
    From
    Israel
    Posts
    4

    Graph theory - Euler or not

    I've stumbled upon this question in Discrete math:
    G is a simple graph with Vertices labeled {1,2,3,4,5,6,7}. It is given that G is Euler (that is, G has a Euler circuit) It is also given that there is no edge between vertices 1 and 2, 2 and 3, and 1 and 3. If we add G those edges, the graph we get is:

    1. Euler (that is, still contains a euler circuit)
    2. Not Euler, but contains a Eulerian trail.
    3. Not Euler, no Eulerian trail.
    4. Might be Euler, might not be. It depends on the original graph G
    5. It is not possible that G is Euler, because according to the data given, it is not a connected graph.

    I think it's number 4, because I could draw the graph G in multiple ways according to the given Data, sometimes Getting a Euler circuit and sometimes not. However, I'm not sure about it. Mainly because I don't know whether it is Critical that a graph be connected for it to be Euler (they usually refer to connected graphs, but it's unclear whether it's critical for the definition of Euler).
    Help would be much appreciated
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Graph theory - Euler or not

    The problem statement says that the the degree of every vertex is even in the original graph. Added edges preserve this property. If Eulerian means the existence of a Eulerian cycle, then the original graph is connected; therefore, the resulting graph is also connected and since all degrees are even, a Eulerian cycle exists there as well. If Eulerian means that all degrees are even, then this is also true in the resulting graph.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2017
    From
    Israel
    Posts
    4

    Re: Graph theory - Euler or not

    Thanks for the answer!
    Though, can't there be a Eulerian Cycle without the original graph being connected? Say if vertex 1-3 is disconnected from the rest, and vertex 4-7 is an Eulerian Cycle?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Graph theory - Euler or not

    I addressed this: If Eulerian graph means that all degrees are even (but the graph is not necessarily connected), then this is also true in the resulting graph. That is, whether the original graph is Eulerian in the strong or the weak sense, the resulting graph is Eulerian in the same sense.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jun 2017
    From
    Israel
    Posts
    4

    Re: Graph theory - Euler or not

    Yes you're right, I'm sorry I've been over this for some time now, so It got a little bit mixed up in my head.

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,203
    Thanks
    2628
    Awards
    1

    Re: Graph theory - Euler or not

    Quote Originally Posted by coacherez View Post
    Though, can't there be a Eulerian Cycle without the original graph being connected? Say if vertex 1-3 is disconnected from the rest, and vertex 4-7 is an Eulerian Cycle?
    All depends upon definitions. Have a look at this , in particular points one & two under properties.

    Now look at these two graphs:
    Attachment 37751 Attachment 37752

    The first graph meets all requirements given in the problem. It contains an Eulerian Cycle any trace includes every edge exactly once and begins and ends at the same vertex. However, it is not connected. It contains vertices of degree zero.

    The second graph does not meets all requirements given in the problem. It does not contains an Eulerian Cycle. However, it is not connected. It does not contains vertices of degree zero.
    Graph theory - Euler or not-x1.gifGraph theory - Euler or not-x2.gif
    Last edited by Plato; Jun 9th 2017 at 06:47 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jun 2017
    From
    Israel
    Posts
    4

    Re: Graph theory - Euler or not

    Precisely, It depends upon definitions. I'm pretty sure it's answer number 1, however I might just have to make sure with my instructors. Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2011, 09:59 AM
  2. Replies: 0
    Last Post: Sep 25th 2010, 05:59 AM
  3. Replies: 0
    Last Post: Feb 20th 2010, 08:26 AM
  4. Euler Path and Graph
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 26th 2009, 07:00 AM

/mathhelpforum @mathhelpforum