1. Hamiltonian circuit: A circuit that uses every vertex in a graph once and only once (except the starting vertex)

2.
         
i				    ii

iii			       iv

a. i is a spanning tree
   ii is not a tree because it has a circuit
   iii is not a tree because not connected, 
   iv is not a spanning tree because it doesn’t span

b. none of them are Hamiltonian circuits because none of them are circuits.

3.  “Brute force method” is the only method studied that guarantees a minimum cost Hamiltonian circuit. 

  The Brute force method is:
    Find all Hamiltonian Circuits.
    Find the cost (add total weights of edges used) of each circuit.
    Choose the one with least cost.

It isn’t always used because of the amount of time it would take to find all Hamiltonian circuits. (In a complete graph with n vertices, there are (n – 1)!/2 different Hamiltonian circuits; because of the factorial, this will quickly become a large number.)

4. 
a. sorted-edge algorithm:
we select edges of least cost first, but still must ensure that each vertex is connected by no more than two edges.
Choose edges in order: DC, AE, AB, BD (AD will put e on a vertex) , EC (it is the only choice left to close the circuit)

b. nearest-neighbor algorithm:  
Beginning with A, take the nearest path to the next vertex, without visiting the same vertex twice.
Choose edges in order order: AE, EB, BD, DC, CA

c. Kruskal’s algorithm:
Add links in order of cheapest cost, such that no circuits are formed. Stop when every vertex is connected.  Choose edges in order order: DC, AE, AB, AD (EB can’t be chosen, it will form a circuit)

5. 
a.  Choose edges in order: AB, BC, (choose CG or BG –here we take CG, now we can’t take BG, or it will form a circuit, we can’t take AG, it will form a circuit), take CD, DF, EF, (DG and FG will both form circuits) take either FH or GH.

b.  This is not the only minimum cost spanning tree. Here is an alternate minimum cost spanning tree, if we choose BG instead of CG in step 3. (We could also replace FH with GH in the last step of the first tree, or replace GH with FH in this tree.)

6. 
a. Sorted Edges 						b. Nearest Neighbor
Choose edges in order: AD, AB, AD, (AE can’t be	Choose edges in order: AD, DE, (EA can’t be 
Chosen, it will put 3 edges on a vertex; same for 	chosen, it will close the circuit too soon) EB, 
BE and AC), BC, CE  					BC, CA

7. a.    3∙5∙2∙4 = 120 (outfits)

   b.    Outfits with blue coat: 5∙2∙4 = 40, outfits with a different coat 2∙4∙2∙4 = 64, total: 104

8. a.  3∙4∙6 = 72 (outfits) 

   b.  4∙4∙6 = 96  (outfits)

9. 26∙(105-1) = 2.59994×1011 (we subtract one from 105 because 00000 is not a valid combination of numbers)