91Ó°ÊÓ

Explain how backtracking can be used to find a Hamilton path or circuit in a graph.

A spanning forest of a graph \(G\) is a forest that contains every vertex of \(G\) such that two vertices are in the same tree of the forest when there is a path in \(G\) between these two vertices. $$ \text { Show that every finite simple graph has a spanning forest. } $$

A spanning forest of a graph \(G\) is a forest that contains every vertex of \(G\) such that two vertices are in the same tree of the forest when there is a path in \(G\) between these two vertices. $$ \begin{array}{l}{\text { Explain how to use breadth-first search to find the length }} \\ {\text { of a shortest path between two vertices in an undirected }} \\ {\text { graph. }}\end{array} $$

Suppose that we vary the payoff to the winning player in the game of nim so that the payoff is n dollars when n is the number of legal moves made before a terminal position is reached. Find the payoff to the first player if the initial position consists of a) two piles with one and three stones, respectively. b) two piles with two and four stones, respectively. c) three piles with one, two, and three stones, respectively.

A labeled tree is a tree where each vertex is assigned a label. Two labeled trees are considered isomorphic when there is an isomorphism between them that preserves the labels of vertices. How many nonisomorphic trees are there with three vertices labeled with different integers from the set \(\\{1,2,3\\} ?\) How many nonisomorphic trees are there with four vertices labeled with different integers from the set \(\\{1,2,3,4\\} ?\)

Show that a tree has either one center or two centers that are adjacent.

Let \(T_{1}\) and \(T_{2}\) be spanning trees of a graph. The distance between \(T_{1}\) and \(T_{2}\) is the number of edges in \(T_{1}\) and \(T_{2}\) that are not common to \(T_{1}\) and \(T_{2}\) . $$ \begin{array}{l}{\text { Suppose that } T_{1}, T_{2}, \text { and } T_{3} \text { are spanning trees of the sim- }} \\ {\text { ple graph } G . \text { Show that the distance between } T_{1} \text { and } T_{3}} \\ {\text { does not exceed the sum of the distance between } T_{1} \text { and }} \\ {T_{2} \text { and the distance between } T_{2} \text { and } T_{3} .}\end{array} $$