Homework 9 -- Graphs:

1. Do page 423-424, problems 5, 8, 9cd, 13a(with W4,5)b, 14, 20, 21.

2. Do page 445-446 problems 1, 8, and 9.

3. Using the icosahedron graph on p. 445, draw an adjacency matrix and adjacency lists.

4. Using the graph 1c in figure 8.52 on page 445, do the following, find a largest independent set in the graph.

5. Draw a graph with 5 vertices that has degree sequence: 4,3,2,2,1. How many edges are in the graph?

6. A graph with 7 vertices and 10 edges has six vertices of degree a and one of degree b. What is b?

7. Find two nonisomorphic 3-regular graphs, each having six vertices.

8. What is the chromatic number of a path? an even cycle? an odd cycle? K₃? K₆?

9. Arrange the following list of integers into a binary search tree. Assume that the integers are inserted into the tree in the order they are listed here: 24, 17, 20, 26, 9, 4, 103, 73, 35, 3, 91
   
   
10. Tom and his wife attended a party with three other married couples, and some people shook hands. No one shook hands with himself(or herself) or with his (or her) spouse, and nobody shook hands with the same person more than once. After all handshaking was over, Tom asked each person, including his wife, how many hands he or she had shaken. Each answered honestly, and the answers were all different. How many hands did Tom shake? How many hands did his wife shake?
    

True or False (Some of these require thought.)

1. __________ Every Eulerian bipartite graph has an even number of edges.

2. __________ If every vertex in a connected graph G has degree 2, then G is a cycle.

3. __________ The Peterson graph (see page 445, 1d) is bipartite.