5.6: Trees
- Page ID
- 88873
Terminology
A graph is a tree if and only if it is connected and contains no cycles.
A vertex in a tree is a leaf if and only if it has degree one.
A graph \(G\) is a spanning tree of a graph \(H\) if and only if \(G\) is a subgraph of HH that contains all the vertices of \(H\) and is a tree.
Practice
Checkpoint \(\PageIndex{4}\)
Determine which graphs in Figure Figure 5.1.1 are trees.
Checkpoint \(\PageIndex{4}\)
Draw all non-isomorphic trees on 3 vertices.
Checkpoint \(\PageIndex{4}\)
Prove that every tree with at least two vertices has at least one leaf.
Checkpoint \(\PageIndex{4}\)
Draw a tree with 7 vertices. Determine for what \(n\) the tree is \(n\)-connected.
Checkpoint \(\PageIndex{4}\)
Explain why for any tree removal of a leaf produces another tree.
Checkpoint \(\PageIndex{4}\)
Find a spanning tree for every graph in Figure 5.2.43.