Chapter 11: Q18E (page 756)
How many vertices does a full \(5\)-ary tree with \(100\) internal
vertices have?
There is\(501\)vertices.
Over 30 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
What is wrong with the following “proof” using mathematical induction of the statement that every tree with \({\bf{n}}\) vertices has a path of length \({\bf{n - 1}}\). Basis step: Every tree with one vertex clearly has a path of length \(0\). Inductive step: Assume that a tree with \({\bf{n}}\) vertices has a path of length \({\bf{n - 1}}\), which has \({\bf{u}}\) as its terminal vertex. Add a vertex \({\bf{v}}\) and the edge from \({\bf{u}}\)to \({\bf{v}}\). The resulting tree has \({\bf{n + 1}}\) vertices and has a path of length \({\bf{n}}\). This completes the inductive step.
Explain how breadth-first search and how depth-first search can be used to determine whether a graph is bipartite.
Show that every tree is bipartite.
Show that the first step of Sollin’s algorithm produces a forest containing at least \(\left\lceil {\frac{n}{2}} \right\rceil \) edges when the input isan undirected graph with \(n\) vertices.
Which of these graphs are trees?
What do you think about this solution?
We value your feedback to improve our textbook solutions.
