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? 
    The chromatic number is 4 because the graph contains a K4 
(D, E, F, and G.)

  3. State the 4-color theorem. How was it proved? Why is there still a search for a better proof? 
    Theorem. Any planar graph is 4-colorable.
    
The theorem was proved by exhaustive checking of over 1900 cases.  A
computer program was used to do it, which makes the proof difficult for
other people to understand.  People are still looking for a "human"
proof.
  4. What is the chromatic number of the following graph? What makes it possible to have such a small chromatic number?
    The chromatic number is 2 because the graph is made up of paths and
contains no cycles.
  5. What is the chromatic number of the following graph? Is this graph planar?
    The chromatic number is 2.  No, the graph is not planar.  This graph
is named K3,3 and is an example of a "bipartite" graph.  The 
vertices of a bipartite graph can be divided into two groups in such 
a way that there are no edges between any two vertices that are in 
the same group.  In the graph above, all the edges are between a 
vertex in the top group and a vertex in the bottom group.  Thus all 
the vertices in the top group can be colored one color, and all the 
other vertices can be colored a different color.

  6. What is the chromatic number of a path? an even cycle? an odd cycle? K3? K6? 
    A path has chromatic number 2, an even cycle has chromatic number 2,
an odd cycle has chromatic number 3, K3 has chromatic number
3, and K6 has chromatic number 6.

  7. What property must be true in order for a graph to contain an Euler trail? 
    Either every node must have even degree or there may be exactly two odd
nodes.
  8. Is there an Euler trail in a K3? K4? 
    There is an Euler trail in a K3 because every vertex has degree
2, but there is no Euler trail in a K4.
  9. Is there an Euler trail in the following graph? 

    Yes, there is.  Start at one of the odd nodes and go to the other.
  10. Does the above graph contain a K4? Explain why a graph can contain a K4 and still have an Euler trail. 
    Edges have been added to the graph so that there are only two odd nodes
in the whole graph.  Three of the nodes in the K4 have been
given extra edges to make them even.
  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

  12. Use the binary search tree you drew to list the elements in sorted order.
    2, 8, 14, 16, 17, 19, 35, 42, 49, 50, 59, 67, 77, 86, 91
  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: G, B, A, D, C, H, F, E

    breadth-first ordering: G, B, C, D, H, A, E, F

  15. What is the size of a maximal independent set in a K3? K4?
    One, in both cases.  Every node in a complete graph is adjacent 
to every other node.
  16. What is the size of a maximal independent set in the following graph? Identify a set of that size.


    size ______6___________

    a maximal independent set____C, B, E, F, H, I________________