Results 1 to 7 of 7

Math Help - Prove That a graph G which is a tree is not an eulerean Graph

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    98
    Awards
    1

    Prove That a graph G which is a tree is not an eulerean Graph

    If G is a tree it has no cycles


    My attempt
    Assume G is a tree

    If G has an Eulerian Circuit then the Eulerian Circuit Must repeat a vertex other than the initial vertex for G to remain a Tree

    therefore there is one vertex which has no bridge.

    -> it is not a tree

    This is not explained as well as I could do.

    Maybe there is a much simpler way of showing this.

    Please advise thanks you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    A Eulerian circuit is a loop, but trees have no loops. QED.

    (Although that is just a shorthand for what you wrote. I can't think of an easier way...)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    98
    Awards
    1
    Thanks , We have not defined a loop. In our definition a tree has no cycles but it does not say it cannot have a circuit.

    Cycle ( A closed walk where no vertex is repeated)
    Circuit ( A closed walk in which no edge is repeated)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Niall101 View Post
    Thanks , We have not defined a loop. In our definition a tree has no cycles but it does not say it cannot have a circuit.

    Cycle ( A closed walk where no vertex is repeated)
    Circuit ( A closed walk in which no edge is repeated)
    no cycles is stronger than no circuits. However, a tree is defined to be a graph with no closed walks...

    Earlier, by 'loop' I meant a closed walk.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2008
    Posts
    98
    Awards
    1
    Can I say that if it has an Eulerean Graph Then the Uniqueness of the path that connects pairs of vertices is no longer present therefore it cannot be a tree

    are all circuits also cycles?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Niall101 View Post
    Can I say that if it has an Eulerean Graph Then the Uniqueness of the path that connects pairs of vertices is no longer present therefore it cannot be a tree
    Yes, although you should point out that it doesn't exist because there are no such paths. The uniqueness isn't the problem, the finding of a path is.

    Quote Originally Posted by Niall101 View Post
    are all circuits also cycles?
    No, cycles are circuits (if not vertices are repeater then no edges are repeated).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2008
    Posts
    98
    Awards
    1
    I have found another solution which doesnt rely on circuits or cycles

    The number of edges in a tree is n-1
    The sum of the degress of the vertices is then 2(n-1) = 2n-2

    To have a eulerian graph The degree of every vertex must be even

    So Sum of the degress of vertives >= 2n

    But 2n-2 is never >= 2n

    therefore it cannot be a tree.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory:Tree
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 22nd 2011, 04:23 PM
  2. Every connected graph contains a maximal tree
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 4th 2011, 06:44 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. graph + tree
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 4th 2010, 11:27 PM
  5. simple graph is a tree?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 07:45 AM

Search Tags


/mathhelpforum @mathhelpforum