I. The Konigsberg Bridge ProblemII. Map ColoringII. Using Euler’s TheoremChild Is not allowed to play with5. A company is trying to schedule people to work on projects together. For various reasons, some people cannot work together. For example, Ann cannot work with Clay, Henry or Ina, because she will be on vacation for a major part of the time they have to work. Dan cannot work with Clay or Julio, because he has said he’ll quit if has to work with them! Here is the list of people who can not work together:Name:________________________________ KO 10/03Group Members:___________________________________________________Graph Theory Project12 points.Each of the problems in this project must be accompanied by a graph.2 pointsI. The Konigsberg Bridge Problem1. a. Draw a graph of the town of Konigsberg. Add or subtract as many bridges as you like until you have a graph where you can go over every bridge exactly once. Write the degreenext to each vertex.b. Discuss with your group various other maps of Konigsberg that also work. Draw three of those graphs here. Write the degree next to each vertex.c. In your group, discuss how many odd vertices and how many even vertices each graph has. Report your results here.d. Are there any graphs where you can start at one spot in town, cross over each bridge exactly once, and return to the start? How many even and how many odd vertices do those graphs have?e. In the original map of Konigsberg, in which you cannot cross every bridge exactly once,how many odd vertices do you have? How many even?f. In your group, make a guess as to what pattern connects these graphs.1 pointsII. Map Coloring2. a. Draw a graph representing the map of the South Eastern United States outlined below.Each state is a vertex, or dot. Connect two vertices with an edge, or line, if the two states share a border. Please label each vertex with the abbreviation for the state (Tx for Texas, etc.). b. Color the vertices of your graph, so that you use the smallest number of colors possible. Use the instructions in the supplement. c. Use the results of coloring your graph to color the map of the outlined states.The South Eastern United States:Oaklahoma North Carolina TennesseeArkansas South CarolinaMiss. GeorgiaAlabamaLouisiana TexasFloridaDraw your graph here or on attached paper:Caution: to get credit for this problem, you must show the graph, with the degree and color of each vertex labeled, and you must show the colored map.1 points3. a. Draw a graph representing the drawing, below.b. Color the graph using the given graph coloring techniques.c. Color the drawing using these same colors as on your graph.Caution: to get credit for this problem, you must show the graph, with the degree and color of each vertex labeled, and you must show the colored picture.Your graph:ABCDEFGHIJII. Using Euler’s Theorem2 points4. Use a graph to determine whether there is a path through these rooms that goes through every doorway exactly once. a. Draw the graph. Each room should be a vertex. Each door corresponds to an edge. (If there are two doors that lead from one room to another, there should be two edges.) Remember, as in the homework, you should include one vertex for the outside. This is different than what your book does. Every door that leads to the outside should be represented by an edge. b. If there is such a path, state what the path would be. c. Explain how you know whether or not there is a path using Euler’s theorem. Hall OutsideLR DR KitchenYour graph:Caution: to get credit for this problem, you must show the graph, with the degree of each vertex labeledIII. Solving Problems using Graph ColoringEach of the next three problems may be solved by creating a graph where vertices join things that are NOT supposed to be together. Then, when you color the graph, each separate color will represent items that are allowed to be together.Example: The following children are not allowed to play together in the daycare (because they BITE each other!):Child Is not allowed to play withCorrin Eric, AnnBeth Ann, WilliamEric WilliamSam Corrin, BethSample GraphYour graph should look as follows, with the same kind of coloring strategy as used in the previous problems. Notice the degree and color next to each vertex.Corrin 3 BlueEric 2 Red Ann 2 Red Sam 2 RedBeth 3 BlueWilliam 2 GreenAnswer: Three groups are needed. Corrin can play in the Blue play group, Eric, Ann and Sam can be in the Red group together, and William can be in the Green group. Now none of the biting kids are together!For problems 5, 6 and 7, show your graphs, follow the map coloring steps and write out the answer to each problem, as it is written in the box in the example.2 points5. A company is trying to schedule people to work on projects together. For various reasons, some people cannot work together. For example, Ann cannot work with Clay, Henry or Ina, because she will be on vacation for a major part of the time they have to work. Dan cannot work with Clay or Julio, because he has said he’ll quit if has to work with them! Here is the list of people who can not work together: Employee Cannot work with Ann Clay, Henry, InaBoris Clay, Fran, Henry, JulioClay Ann, Boris, Dan, Fran, Henry, GlynDan Clay, JulioEmilio Glyn, Henry, InaFran Boris, ClayGlyn Clay, EmilioHenry Ann, Boris, Clay, EmilioIna Ann, EmilioJulio Boris, Dana. Create a graph. Each employee should be a vertex. Label each vertex with the initial or nameof the person. Join the employees with an edge if they can not work with each other. Write thedegree of each vertex on the graph, then color the graph.b. Based on your graph coloring, what is the smallest number of work groups necessary? Which employees would be in each group? (Follow the example on the previous page.)Caution: to get credit for this problem and the next ones, you must show the graph, with the degree and color of each vertex labeled, and you must write the answer to the problem.2 points6. A college wants to schedule courses. It is offering Math 01, Math 02, Math 120, English 01, English 02, English 120, History 120, History 200, and Spanish 120. No math class should given at the same time as any English class, in case a student needs to take both Math and English. No 120 class should be offered at the same time as another 120 class, because students often need to take several 120 classes. a. Complete the chart, below:Course Cannot be