Problem Set VII, for Monday, May 18

Mathematics 61, section 1

Planar Graphs:

• Exercise 16, but assume that G has exactly eleven vertices.   (Then the problem does not require a star.   Suggestion: See Exercise 13, which will be done in class.)
• Exercise 23.

Introduction (to Trees):

• Exercise 5.
• Exercise 10.  
• Exercise 30.   Can we conclude that the tree must have at least two vertices of degree 1?   Why or why not?
• Exercise 31: Trees are planar.

Terminology and Characterizations of Trees:

• Exercise 26.
• Find all values of n such that there is a simple graph G with n vertices for which both G and its complement are trees.
• Assume that G is a simple graph and v is a vertex of degree 3 in G.   Prove that either G or its complement contains a triangle (i.e., a K_3 subgraph).

Isomorphisms of Trees:

• Exercise 3.
• Exercise 8.

Remark on Huffman codes: Huffman codes were invented by David Huffman, the result of a term paper he wrote while a graduate student at MIT in the 1950's.   He later taught at UC Santa Cruz.   Huffman codes are widely used for data compression.

Click here for answers in .pdf format.