Results 1 to 3 of 3

Math Help - Simple graph theory, but can't figure out what they're looking for

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Simple graph theory, but can't figure out what they're looking for

    Let A and B be 2 Eulerian graphs with no common vertices. Let v1 be a vertex of A and v2 be a vertex of B. Let G be the graph that is formed by taking AUB and adding the edge v1v2. What can be said about G?

    Is it simply that G is Eulerian since we are just adding one more edge and we are not changing the number of vertices, or is there something else that can be said?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,797
    Thanks
    1689
    Awards
    1
    Quote Originally Posted by zhupolongjoe View Post
    Let A and B be 2 Eulerian graphs with no common vertices. Let v1 be a vertex of A and v2 be a vertex of B. Let G be the graph that is formed by taking AUB and adding the edge v1v2. What can be said about G?
    It seems that I have given this warning several times today: There are no standard notations.
    Usually we say that a graph is Eulerian if it has an Eulerian circuit (all vertices of even degree).
    But there are texts that use the term if a graph is simply traceable.

    If you have two disjoint graphs of all even vertices then by connecting them with one edge, you have introduced two odd vertices. Therefore the new graph is not Eulerian but it is traceable.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    Thanks. I see the distinction there that is used. My book uses the Eulerian circuit vs. Eulerian trail.
    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: November 15th 2011, 09:59 AM
  2. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  3. simple question ... just can't figure it out
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 11th 2009, 01:56 PM
  4. simple graph theory
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 29th 2008, 04:31 PM
  5. Replies: 3
    Last Post: August 27th 2007, 06:15 PM

Search Tags


/mathhelpforum @mathhelpforum