Practice question · Select all that apply
Select every statement that must be true of any tree with n vertices.
Hints
- Go back to the two defining conditions and work out what each one forces.
- Draw a tree with three vertices in a line and check each claim against it.
Show the answer
- A. There is exactly one path between any two of its vertices
- C. It is connected
- D. It has exactly n minus 1 edges
Why
A tree is connected and acyclic, which gives exactly n - 1 edges and a unique path between any two vertices, a second path would close a cycle. It contains no cycle at all, and its leaves have degree 1, so a three-vertex path graph refutes the second option immediately.
Practise Graphs and Trees
The app has 4 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Graphs and Trees
- A social network is a graph, a filesystem is a tree, and a tree is a graph. What does the extra restriction…
- Sort each term or description by what it is a property of.
- The handshaking lemma says the degrees of all vertices sum to twice the number of edges. Why must the total…
- A connected graph with 8 vertices and 8 edges must contain a cycle.