Q2 Handshake Theorem
10 Points
(a) Clearly state the Handshake Theorem (also known as Euler’s Sum of Degrees Formula.) Explain in your own words (i.e. not copying from any previous source) why it is true.

(b) Write down five whole numbers that, if they were claimed to be the degrees of the vertices of a graph, would contradict the Handshake Theorem (meaning that a graph on 5 vertices with these degrees could not exist.)

PLEASE SELECT FILE(S)SELECT FILE(S)

Save Answer

Q3 Pascal’s Triangle
10 Points
(a) How many grapefruits are there stacked in a triangular based pyramid with all equal sides (also known as a tetrahedron) that is 7 layers tall. Explain how to use Pascal’s Triangle to find this, and show your work.

(b) Compute (x+y)6 in expanded form. Explain how to use Pascal’s Triangle to find the answer.

PLEASE SELECT FILE(S)SELECT FILE(S)

Save Answer

Q4 Repeated Nearest Neighbor
10 Points
Q4_NNA_CLA.JPG

(a) How do we know that the graph depicted has a Hamilton circuit? How many Hamilton circuits does it have?

(b) Perform the Repeated Nearest Neighbor Algorithm on this graph. For each starting vertex, write down the edge list of the circuit and its total weight. What circuit does Repeated NNA prescribe?

Q5 Identification Polygons
10 Points
mobius_poly.png

(a) Depicted is the identification polygon for the Möbius band. Using a strip of paper (you will probably want something more rectangular than square in shape) make your own Möbius band. Take a clear picture showing the labeled, directed edges and how you joined them.

(b) Starting at any point on your Möbius band, begin drawing a line along the strip and continue it until it joins back up to itself, thus showing that the Möbius band has only one side and hence is not orientable.