Practice Homework 6 -- Graphs

1. Draw the graph corresponding to the following map:
   
2. What is the chromatic number of the graph you drew above?

3. State the 4-color theorem. How was it proved? Why is there still a search for a better proof?

4. What is the chromatic number of the following graph? What makes it possible to have such a small chromatic number?
   

5. What is the chromatic number of the following graph? Is this graph planar?
   

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

7. What property must be true in order for a graph to contain an Euler trail?
   
   

8. Is there an Euler trail in a K₃? K₄?
   
   

9. Is there an Euler trail in the following graph?
   

10. Does the above graph contain a K₄? Explain why a graph can contain a K₄ and still have an Euler trail.
    
    

11. 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.
    35, 14, 19, 67, 50, 42, 59, 49, 8, 17, 91, 86, 77, 16, 2, 44
    
    
    
    
    
    

12. Use the binary search tree you drew to list the elements in sorted order.
    
    
    
    

13. Find a minimum spanning tree in the following graph.
    

14. Start at vertex G of the following graph, use alphabetical order as a tie-breaker, and write down both a depth-first and a breadth-first traversal ordering.
    

    depth-first ordering_______________________________________________
    
    breadth-first ordering______________________________________________
    

15. What is the size of a maximum independent set in a K₃? K₄?
    
    

16. What is the size of a maximum independent set in the following graph? Identify a set of that size.
    

    
    a maximum independent set__________________________________