Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By Mezza

Thread: Trees

  1. #1
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    Trees

    Why is the following graph not a tree? How many edges do you have to delete to makeit a tree?

    Trees-trees.png

    The following graph is not a tree because there are cycles in it.The definition of a tree is a connected graph without cycles in it.
    I'd have to delete 4 edges to make a tree right?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,267
    Thanks
    2641
    Awards
    1

    Re: Trees

    Quote Originally Posted by bee77 View Post
    Why is the following graph not a tree? How many edges do you have to delete to makeit a tree?
    Click image for larger version. 

Name:	trees.PNG 
Views:	1 
Size:	11.1 KB 
ID:	38081
    The following graph is not a tree because there are cycles in it.The definition of a tree is a connected graph without cycles in it. I'd have to delete 4 edges to make a tree right?
    any acyclic connected graph is a tree. SEE HERE

    In the given graph there are six 'triangles' so delete six edges.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2017
    From
    Yeah onya
    Posts
    7
    Thanks
    4

    Re: Trees

    Quote Originally Posted by Plato View Post
    any acyclic connected graph is a tree. SEE HERE

    In the given graph there are six 'triangles' so delete six edges.
    I was gonna post something to help; but, there it is.

    If it helps bee77; "triangles" (three vertices are in use) in a graph make cycles. You want to get rid of the "triangles".
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2017
    From
    Yeah onya
    Posts
    7
    Thanks
    4

    Re: Trees

    Also, a tree has n vertices and n - 1 edges. This makes it very easy.
    Thanks from bee77
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How Many Trees?
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: Sep 12th 2010, 09:52 PM
  2. Trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 21st 2009, 12:00 PM
  3. how can you plant 10 trees in 5 rows of 4 trees each?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Dec 22nd 2008, 11:43 AM
  4. Trees
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 6th 2008, 03:27 PM
  5. trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 22nd 2007, 09:22 AM

/mathhelpforum @mathhelpforum