16.8: Exercises

Exercise $\PageIndex{1}$

Prove that if a graph contains a closed trail then it also contains a proper cycle.

Spanning trees.

For each of the graphs in Exercises 2–3, draw a spanning tree by inspection.

Exercise $\PageIndex{2}$

Figure $\PageIndex{1}$

Exercise $\PageIndex{3}$

Figure $\PageIndex{2}$

Reducing to a spanning tree.

For each of the graphs in Exercises 4–5, use the following algorithm to obtain a spanning tree.

• If the graph contains a proper cycle, remove one edge of that cycle.
• If the resulting subgraph contains a proper cycle, remove one edge of that cycle.
• If the resulting subgraph contains a proper cycle, remove one edge of that cycle.
• etc..
• Continue until there are no proper cycles left.

Exercise $\PageIndex{4}$

Figure $\PageIndex{3}$

Exercise $\PageIndex{5}$

Figure $\PageIndex{4}$

Depth-first and breadth-first spanning trees.

For each of the graphs in Exercises 6–8, determine both a depth-first and breadth-first spanning tree. Use any vertex you like as the starting node.

Exercise $\PageIndex{6}$

Figure $\PageIndex{5}$

Exercise $\PageIndex{7}$

Figure $\PageIndex{6}$

Exercise $\PageIndex{8}$

Figure $\PageIndex{7}$