Trees and spanning trees
The tree as a connected graph without cycles, its characterisations (n − 1 edges, a single path between two vertices), forests, leaves, rooted trees and the spanning tree of a connected graph.
- 29 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Understand
A few cards from the deck
Tree: what is it?
Show the answer
A connected graph with no cycle.
Both conditions matter: the graph A-B, B-C, C-A, D-E is neither connected nor free of cycles. With n vertices, a tree has exactly n − 1 edges.
A connected graph has 7 vertices and 7 edges. Is it a tree?
- No, it contains a cycle: 7 edges is one too many
- Yes, since it is connected, no other condition is needed
- No, a tree must have as many edges as vertices
- Yes, as soon as a root can be chosen among its vertices
Show the answer
No, it contains a cycle: 7 edges is one too many
A tree with 7 vertices has 6 edges. A connected graph with 7 has one edge too many, hence a cycle. Choosing a root is always possible and proves nothing.
A tree with n vertices has exactly … edges; a forest of n vertices made of k trees has ….
Show the answer
A tree with n vertices has exactly n − 1 edges; a forest of n vertices made of k trees has n − k.
Each tree in the forest has one more vertex than edges: summing over the k trees, k edges are missing.
Forest: what is it?
Show the answer
A graph with no cycle, connected or not: each of its connected components is a tree.
A forest of n vertices made of k trees has n − k edges. A tree is the special case k = 1.