Exercise · ZW-TREE-003 · ★☆☆ Basic
The vertices are \(1,\dots,5\). Which of these edge sets forms a tree?
Choose one option.
Show answer
- A. \(12,23,34,45\)
Explanation
The path \(12,23,34,45\) is connected and acyclic. The set \(12,23,31,45\) has the cycle \(1,2,3\) and is not connected; \(12,23,34\) leaves vertex 5 isolated; and \(12,23,34,45,51\) is a cycle.
Review the concept: Tree
A tree \(T=(V,E)\) is a connected graph that contains no cycles.
\[|E|=|V|-1\]
More practice problems: tree
- ZW-TREE-001 How many edges does a tree with 10 vertices have?
- ZW-TREE-002 A tree has 15 edges. How many vertices does it have?
- ZW-TREE-004 What is the sum of the vertex degrees of a tree with 7 vertices?
- ZW-TREE-005 A tree with 7 vertices has one vertex of degree 4, one of degree 3, and the rest are leaves (degree…
- ZW-TREE-006 One edge is removed from a tree. How many connected components does the resulting graph have?
- ZW-TREE-007 How many different trees are there on labeled vertices 1,2,3,4?
- ZW-TREE-008 An acyclic graph has 10 vertices and 3 connected components. How many edges must be added, without…
- ZW-TREE-009 An edge is added to a tree between two vertices that were not adjacent. The result: