1. ## Trees

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

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?

2. ## Re: Trees

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

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.

3. ## Re: Trees

Originally Posted by Plato
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".

4. ## Re: Trees

Also, a tree has n vertices and n - 1 edges. This makes it very easy.