1. Show that every connected graph has at least one spanning tree by giving an algorithm for finding one.
2. Did your algorithm begin with just the vertices, or did it begin with the whole graph? Find a second algorithm that begins differently than your first.
3. Prove that your algorithms work. That is, show that the output is a tree and that the tree includes all the vertices of the original graph.