Problem 1076

Determine whether the graph is a tree. If the graph is not a tree, give the reason why.




A tree is a graph that is connected and has no circuit. All trees have the properties listed below.

a. There is no one and only one path joining any two vertices.

b.Every edge is a bridge.

c.A tree with n vertices must have n – 1 edges.


First, determine whether the given graph is connected. All vertices A, B, C, and D can be reached from all other vertices, so the graph is connected.

Next, determine whether the graph has circuits. The graph contains the circuit A, B, C, D.

There is more than one path connecting each vertex to the other vertices.


The graph is connected, but it has a circuit. Therefore, the graph is not a tree. Note that is any one of the edges were removed, the circuit would be broken and the graph would be a tree.



Leave a Reply

Your email address will not be published. Required fields are marked *