Graph Theory Test Review SheetAnswers are at the end.Many of the questions on this review sheet refer to the pictures and problems in the Chapter Test, p. 876, of your textbook.1. Look at the map on p. 876, for problem 2. If you had an atlas, you could see that an ocean touches all the countries except Burkina Faso. For the purposes of this map coloring, treat the ocean as if it is a country (since when you color a map, you must color the oceans, too). a. Draw a graph representing this new map, where each vertex represents a country (or the ocean), and each edge represents a common border. Label each vertex withthe name of the country and the degree of the vertex.b. Which vertex has the highest degree? Explain.c. Color the graph, so that no two connected vertices have the same color. Which vertex should you color first? Second? Third?d. What is the last vertex colored? Why? e. There is a theorem which tells the largest number of colors needed to color any map like this one. Name the theorem. Does your map coloring agree with this theorem? Explain.2. Look at the floor plan for problem #5. a. Create a graph with each room of the floor plan represented by a vertex, with two rooms connected by an edge if there is a door between them. Label the degree of each vertex. Treat the "outside" as if it is another room.b. Does your graph have an Euler path? Explain how you know.c. Does your graph have an Euler circuit? Explain how you know.d. Is it possible for a person to walk through each door way exactly once and returnto the room that they started in? If so, indicate how they should go.e. How does your answer to d relate to your answers to b and c? 3. a. Draw a map of a fake city and its bridges, called Mathinsberg, that has an Euler pathbut it does not have an Euler circuit.b. Explain how you can tell that it has an Euler path but no circuit. c. Now change your map, if needed, so that Mathinsberg has an Euler circuit.4. The designer of a new entertainment complex called "Jungle World" wants to include several large enclosures in which wild animals can roam freely about. Obviously if one ofthe animals can harm one another, then those two animals cannot be placed in the same enclosure. Animal Cannot be placed withTiger Antelope, Leopard, OstrichLeopard Antelope, Rhino, Ostrich, TigerAntelope Leopard, TigerRhino Leopard, OstrichOstrich Tiger, Leopard, Rhino, SnakeSnake Ostricha. Draw a graph using the above information. Each animal should be represented by a vertex, and the vertices connected by an edge if the animals can not be placed inthe same enclosure. Label each vertex with the name of the animal and write the degree of each vertex.b. Color the graph with the smallest number of colors possible. Which vertex should you color first? Second? Third?c. Which vertex should you color last? Why?d. Determine the smallest number of enclosures necessary for the animals, and tell how you would assign the animals to these enclosures. 5. a. Draw a complete graph, with five vertices A, B, C, D, and E, and the degree of each vertex labeled. b. Does this graph have an Euler circuit? Explain how you know, and if it does, say what the circuit would be.c. Does this graph have a Hamilton circuit? Explain how you know, and if it does, say what the circuit would be.d. Does this graph have an Euler path? Explain how you know, and if it does, say what the path would be.e. Does this graph have a Hamilton path? Explain how you know, and if it does, saywhat the path would be.f. How many Hamilton circuits does the graph have? 6. Suppose you have a complete graph with six vertices. Would any of your answers to the previous question be different? Explain how you know for each part (a through f) above.7. Do problems p. 876, #8, 9 Answers1. a. Graphs may vary slightly in how they look, but no matter how you draw the graph, it should have degrees as follows: Sierra Leone - deg. 2, Liberia - deg. 3, Ivory Coast - deg. 4, Burkina Faso -- deg. 4, Ghana -- deg. 4, Togo -- deg. 4, Benin, deg. 3, Ocean - deg. 6.b. The ocean - it touches 6 countries.c. Color the ocean first, then the Ivory Coast and Ghana and Togo, since both have high degree and are connected to the ocean.d. Color Burkina Faso last because all vertices connected to the one with highest degree (the ocean) should be colored first.e. The four-color theorem says any map can be colored in four or fewer colors. This particular map can be colored in three colors, so that does agree with the fourcolor theorem.2. a. Graphs may vary slightly in how they look, but no matter how you draw you graph, degrees should be as follows: Outside - deg. 2, A - deg. 4, B - deg. 4, C - deg. 2, D deg. 4, E - deg. 2.b. Yes, all the vertices are of even degree (2 and 4 are both even numbers).c. Yes, same reason .d. Yes, here's one: start at A, then go C, D, E, B, D, A, B, A. There are many others.e. It's the same as asking if there's an Euler circuit.3. a. Answers will vary.b. To have an Euler path but no circuit, all but two of your islands or pieces of land must have an even number of bridges coming from them. Two of the lands must have an odd number of bridges coming from them (those bridges will be the start and end of your walk).b. Connected the two pieces of land that are of odd degree with a new bridge (or take away a bridge that connectes them) Now each has an even number of bridges.4. a. Graphs may vary slightly in how they look, but no matter how you draw your graph, degrees should be as follows: Tiger - deg. 3, Leopard - deg. 4, Rhino - deg. 2, Ostrich - deg. 4, Antelope - deg. 2, Snake - deg. 1.b. Color the Leopard or Ostrich first, then the Tiger.c. If you color the Leopard first, the Snake will be last, since is not connected to the Leopard. If you color the Ostrich first, the Antelope will be last. c. Answers will vary, but all should be able to do it with only three enclosures. Using the colors green, blue and red, I colored the Ostrich and Antelope both green, so they could go together in a cage. I colored the Tiger, Rhino and Snake red, so they could go together in a cage. I colored the Leopard blue, so it got its own cage.5. a. A complete graph means every vertex is connected to every other. In this graph, eachvertex will have degree 4, since it is connected to 4 other vertices.b. Yes, it does, because every vertex is even. An Euler circuit visits each edge exactly once and comes back to the start. Here's one possible way: A,B,C,D,E,A,C,E,B,D,A.c.