Distinguish between a tree and a graph; include a key property of a tree.

• A. A tree is a graph that may contain cycles.
• B. A graph is always disconnected.
• C. A tree has a unique path between any two nodes, but may contain cycles.
• D. A tree is an acyclic connected graph with n-1 edges.

Answer: (D)

Trees are connected graphs with no cycles. That combination has a key consequence: for a tree with n nodes, there are exactly n-1 edges. This succinctly captures why a tree is a special kind of graph and why it’s not just any graph. A tree cannot contain cycles, because a cycle would contradict being acyclic, and it must be connected so you can reach every node from every other node.

In light of the statements, the one that best describes a tree is that it is an acyclic connected graph with n-1 edges. The idea that a tree may contain cycles is incorrect, since cycles break acyclicity. The notion that a graph is always disconnected is incorrect because graphs can be connected as well. The idea that a tree has a unique path between two nodes but may contain cycles is also incorrect, since having a cycle would violate acyclicity.