Answer Happy

Determine how you would solve each of the problems using a graph theory technique we discussed: (1) Euler path, (2) Hamilton cycle, (3) proper vertex color- ing/chromatic number, or (4) edge coloring/chromatic index. For each of the 4 problems below, specify the following: • Describe how you would represent the situation as a graph, that is, state what the edges and vertices are in your graph of the problem. • State the technique you would use. (Hint: each technique is used exactly once!) • Briefly explain how your technique answers the given question. (a) An airline has flights into and out of many cities; however, this airline only has direct flights between certain pairs of cities, each with a fixed price. You are planning a trip from Chicago to Tokyo, but the airline does not have a direct flight from Chicago to Tokyo. What is the cheapest flight you can book that leaves from Chicago and arrives in Tokyo? (b) Ten members of Math Club are driving to a math conference in a neighboring state. However, some of these students have dated in the past, and things are still a little awkward. Each student lists which other students they refuse to share a car with; these conflicts are recored in the table below. What is the fewest number of cars the club needs to make the trip? Student: A B C D E F G H I J Conflicts: BEJ ADG HJ BF AI DJ B CIEHJ ACFI (c) You finally achieve your dream and get a ticket to spend an entire day strolling through the art exhibits at the Louvre; however, you are an art fanatic and are worried that one day might not be enough time to soak in the art. You do not want to waste time by visiting a room in the Louvre more than one time, so you plan your route the night before. Is it possible to take a round trip through the Louvre and visit each room exactly one time? (d) You and your friends want to take a tour of the United States by car. You will visit all 50 states but with the following rule: you must cross each border between neighboring states exactly once. For example, you must cross the IL-WI, IL-IA, IL-MO, IL-KY, and IL-IN borders each exactly once. Can you do it? (e) Your Quidditch league has 5 teams. You will play a tournament in which every team will play every other team once. Each team can play at most one match each day, but there is plenty of time in the day for multiple matches. What is the fewest number of days over which the tournament can take place?