HMMT 二月 1998 · 团队赛
HMMT February 1998 — Team Round
题目详情
Power Question - Coloring Graphs Perhaps you have heard of the Four Color Theorem (if not, don’t panic!), which essentially says that any map (e.g. a map of the United States) can be colored with four or fewer colors without giving neighboring regions (e.g. Massachusetts and New Hampshire) the same color. It was, until 22 years ago, one of the most famous unsolved problems in mathematics. The only known proof, however, is so long that it requires a computer to carry it out. This power question will lead you through the basic definitions and theorems of graph theory necessary to prove the Five Color Theorem, a weaker and much easier (though still quite challenging) statement. Part I - Graphs Definitions: A graph is a collection of points and lines (or curves), called vertices and edges , respectively, where each edge connects exactly two distinct vertices and any two vertices are connected by at most one edge. We say that two vertices are adjacent if they are connected by an edge. Notation: For this problem we will denote vertices by capital letters and the edge connecting vertices X and Y by XY. Vertices will be drawn as dots so that they will be distinguishable from edge crossings. We will denote graphs by capital script letters, usually G or H . Example: Here is a graph with vertices A, B, C, D, and edges AB, AC, BC. B D A C a . Which of the following are graphs? List the vertices and edges of each graph and explain why the others are not graphs. [1 point each] i . A B iv . A B C D C D E ii . v . B C A B C A iii . B vi . A B A C E
C D Definition: Graph G is said to be isomorphic (from Greek roots meaning “same structure”) to H , written G ≅ H , if the vertices of G can be given the names of the vertices of H in such a way that G and H have the same edges. This relabling is called an isomorphism and is reversible, thus implying H ≅ G as well. Example: A B B L G ≅ H since we can relable the vertices of G as follows: A ↔ B, B ↔ L, C ↔ U, D ↔ E D C E U (we write the double arrows to emphasize the reversibility of G H the isomorphism). b . [1 point each] i . List the edges of H . ii . Show that H ≅ G in the example by writing an isomorphism from H to G . From now on the diagrams in the problem will not have the vertices explicitly labled unless necessary. Thus to show two unlabled graphs are isomorphic we can arbitrarily lable the vertices of one and then show that the other can be labled with the same names to yield the same edges. c . For each of the following pairs of graphs, state whether or not they are isomorphic (you do not need to justify your answer). [parts i - iii are 1 point each, parts iv - vi are 3 points each] i . iv . and and ii . v . and and iii . vi .
and and A couple more definitions are best given in this section, though there won’t be any questions specifically about them until later. Definitions: A graph H is a subgraph of a graph G if every vertex of H is a vertex of G and every edge of H is an edge of G . The degree of a vertex is the number of edges connected to it. Example: B B H is a subgraph of G . Vertex B has degree 2 in G and degree 1 in H . A C A C G H Part II - Planar Graphs There are not many nontrivial properties possessed by all graphs, so we will restrict our attention to graphs with certain nice properties that we can exploit to prove cool theorems. So now we need one more round of definitions, then the real fun begins! Definitions: A graph is planar if it is isomorphic to a graph that has been drawn in a plane without edge crossings. Otherwise a graph is nonplanar. It shouldn’t be too hard to see that every subgraph of a planar graph is planar. A walk in a graph is a sequence A A ... A of not necessarily distinct vertices 1 2 n in which A is adjacent to A for k = 1, 2, ..., n-1. k k+1 A graph is connected if every pair of vertices is joined by a walk, or equivalently if there is a walk that passes through every vertex at least once. Otherwise a graph is said to be disconnected. When a planar graph is actually drawn in a plane without edge crossings, it cuts the plane into regions called faces of the graph. Example: A R L Is connected since the walk EDWARDEARLY passes through every Y vertex at least once. It has 3 faces (don’t forget the exterior region when counting). W D E
a . How many vertices, edges, and faces do each of the following graphs have? [3 points each] i . ii . b . For each of the following graphs, state whether or not it is planar. You do not need to justify your answer. [3 points each] i . iii . ii . iv . Euler’s formula states if a connected planar graph has v vertices, e edges, and f faces, then v-e+f=2. Proving this would go beyond the scope of this problem, so you may take this formula as given. c . [15 points] Prove that if G is planar and connected with v ≥ 3, then 3 f ≤ e ≤ 3v − 6 . 2 d . Prove that the following graphs are nonplanar. i . [5 points] ii . [10 points] e . [12 points] Prove that every planar graph has at least one vertex of degree 5 or less. Part III - Coloring
Now we can begin talking about coloring planar graphs. Definition: We say a graph has been colored if a color has been assigned to each vertex in such a way that adjacent vertices have different colors. The chromatic number χ (the Greek letter chi, pronounced like sky without the s) of a graph is the smallest number of colors with which it can be colored. Example: Here is a graph with chromatic number 3, colored in b lack, g reen, and r ed. b g r b b a . Calculate χ for each of the following graphs. [3 points each] i . iii . ii . iv . b . [14 points] Given a graph G , let χ be the chromatic number of the graph obtained by taking the vertices of G and drawing edges only between those that are not adjacent in G . Prove that χ + χ ≥ 2 v . c . Assume G is a planar graph with χ >5. i . [5 points] Prove that at least one of the following must be isomorphic to a subgraph of G (where the vertex V is only adjacent to the vertices shown). V V V V V V
ii . [20 points] Prove that if one of the above is a subgraph of G (where the vertex V is only adjacent to the vertices shown) then we can remove one vertex (and all edges touching it) from G to obtain a graph with fewer vertices which also has χ >5 (you may use the Jordan Curve Theorem, which states that a closed loop that does not intersect itself divides the plane into an inside and outside, and if a continuous curve joins a point on the inside to one on the outside then it must cross the loop). iii . [5 points] Prove the Five Color Theorem: Every planar graph has χ ≤5.
解析
1998 Power Question Solutions I. Graphs, total of 20 points a. completely correct gets 1 point, total of 6 points i. yes. vertices A,B,C,D, edges AB,AC,AD,BD ii. no. A and B are connected twice iii. yes. vertices A,B,C, edges ABC iv. yes. vertices A,B,C,D,E, edges AB,AD,AE,BE,CD,CE v. no. the edge from B does not connect to another vertex vi. no. E is connected to itself b. completely correct gets 1 point, total of 2 points i. BL,BE,BU,EL,EU ii. A ↔ B, B ↔ L, C ↔ U, D ↔ E c. 1 point each for i-iii, 3 for iv-vi, total of 12 points i. no ii. no iii. no iv. yes v. no vi. yes note that the second graph in v has more vertices of degree 3 than the first II. Planar Graphs, total of 60 points a. 1 point each for v, e, f, total of 6 points i. v=9, e=16, f=9 ii. v=7, e=14, f=9 note that v-e+f=2 by Euler’s formula b. 3 points each, total of 12 points note that this is a planar drawing of ii: i. yes ii. yes iii. no iv. yes for iii, note that if we remove the two vertices of degree two and make the vertices they were adjacent to adjacent to each other then we get a graph isomorphic to the one in d.ii. c. total of 15 points partial credit: up to 5 for effort, 5 for insight, otherwise as described below [1 point] If G has 3 vertices and two edges then the assertion is easy since f=1. [6 points] Otherwise each face is bounded by 3 or more edges, hence counting the number of edges bounding each faces and summing, then using the fact that we at most double counted [-2 for asserting we exactly double counted] each face we get 3f ≤ 2e, thus proving the left inequality.
[8 points] Now f ≤ (2/3)e and we want to eliminate f, so we can add v-e to both sides to get v-e+f ≤ v-e+(2/3)e, thus by Euler’s formula 2 ≤ v-e/3, and rearranging yields the right inequality. d. 5 points for i, 10 for ii, total of 15 points partial credit: if Jordan curve thm is used then 3 points for i, 5 for ii. on part ii: 3 for effort, 3 for insight, otherwise as described i. Assume it is planar. v=5, e=10, 3v-6=9<e, contradicting c, thus nonplanar ii. [1 point] Note that v=6, e=9, so 3v-6=12>e is not a contradiction [2 points] There are no triangles in this graph, thus every face is bordered by at least 4 edges. This will allow us to prove a better inequality as in c with the assumption the graph is planar, and that will provide the contradiction. [2 points] Thus as in the proof of c we get 4f ≤ 2e. [4 points] Hence f ≤ e/2, and again we want to eliminate f so adding v-e to both sides and applying Euler’s formula yields 2 ≤ v-e/2. (or e ≤ 2v-4) [1 point] 6-9/2<2, contradicting the inequality just proved, thus the graph is not planar. e. total of 12 points partial credit: 4 for effort, 4 for insight, otherwise as described [2 points] Without loss of generality we may assume the graph is connected. [2 points] If the graph has fewer than 3 vertices then the assertion is obvious. [5 points] Otherwise we can apply the inequality in c. First assume every vertex has degree at least 6, then adding the degrees of each vertex double counts the edges so 6v ≤ 2e. [3 points] Now by c. e ≤ 3v-6, and combining these inequalities we get 6v ≤ 6v-12, a contradiction, thus the graph must have at least one vertex of degree 5 or less. III. Coloring, total of 56 points a. 3 points each, total of 12 points i. 4 ii. 5 iii. 4 iv. 3 b. total of 14 points partial credit: 5 for effort, 5 for insight, otherwise as described [8 points] Number the colors used in G 1, 2, ..., χ . Let v be the number of vertices 1 colored with color 1. Then since no pair of them are adjacent, the are all adjacent in the new graph and thus χ ≥ v . Repeating this procedure for v , ..., v and adding we get χχ 1 2 χ ≥ v. [6 points] By the AM-GM inequality χ + χ ≥ 2 χχ ≥ 2 v . c. 5 points for i and iii, 20 for ii, total of 30 points partial credit: as described below i. By II.e. G must have a vertex of degree 5 or less
ii. [2 points] We want to remove the vertex V without decreasing the number of colors needed. In the cases where V has degree < 5 this is obviously possible. [10 points] In the case where V has degree 5, color the adjacent vertices with colors 1, 2, 3, 4, 5 in clockwise order. If the vertices colored 1 and 3 are not connected by a walk with all vertices colored 1 or 3 then change the vertex colored 3 to 1, change any 1 vertices adjacent to it to 3, then change any 3 vertices adjacent to those to 1, and so on. This recoloring does not affect any of the other vertices adjacent to V and thus allows us to make V color 3, i.e. if a sixth color is needed for G then it is still needed after we remove V. [8 points] If the vertices colored 1 and 3 are connected by a walk of vertices colored 1 or 3 then look at the vertices colored 2 and 4. If they are connected by a walk then by the Jordan Curve Theorem [-4 for not using this] this walk must cross the closed curve formed by the 1-3 walk and the edges from V to the vertices colored 1 and 3. The graph is planar, so we can assume it is drawn without edge crossings, thus the walk from the vertex colored 2 to the one colored 4 must cross this curve at a vertex, hence they are not connected by a walk with all vertices colored 2 or 4, and by the previous argument we can change the vertex colored 2 to 4 and make V color 2, so it can be removed without removing the need for a sixth color. iii. [4 points] We have shown that for any graph with χ >5 we can find one with fewer vertices, and since the proof did not depend on the number of vertices we can keep doing this until we get a graph with 5 vertices, which can clearly be colored with only 5 colors, thus G could not require more than 5 colors. [1 points] To make this rigorous some mention should be made of the well-ordering principal or infinite descent. Historical notes and inspiration for further study of the subject: The Four Color theorem was first conjectured in 1852. Many “proofs” were given, including one in 1879 by A. B. Kempe that was believed to be correct until P. J. Heawood found a flaw in 1890. The proof of the Four Color theorem, given in 1976 by Haken and Appel, uses a similar technique to what we just used, but instead of using 6 possible subgraphs it uses 1482. The way these theorems relate to coloring maps is that we can consider the dual graph , formed by putting a vertex in every face and connecting the vertices whose faces share an edge. Coloring the dual graph is the same as coloring the faces of the original graph in such a way that no two faces sharing an edge have the same color, which is what one does when coloring a map. While it may seem that we used many definitions in this power question, there are many more that had to be omitted. Some of the other interesting definitions used in graph theory are expansion , which is what you get if you add vertices along an edge of a graph, and supergraph , which is what you get if you add new vertices anywhere and connect them arbitrarily to the other vertices. Kuratowski’s Theorem states that every nonplanar graph is a supergraph of an expansion of one of the two graphs in II.d. A corollary of this is that a graph is nonplanar iff it is a supergraph of an expansion of one of those two graphs, thus we can classify planar and nonplanar graphs in terms of just two particular graphs.
A planar graph can alo be described as one that can be drawn on a sphere with no edge crossings. A torus is essentially the surface of a solid sphere with a hole drilled all the way through it. The genus g of a graph is the minimum number of holes that must be drilled in a sphere in order to be able to draw it without edge crossings. In other words a graph of genus g can be drawn on a g holed torus without edge crossings, but not on a g-1 holed torus. The Heawood Coloring Theorem states that if G has genus g > 0 then G can 7 + 1 + 48g be colored with colors. Note that plugging in g=0 yields 4, but no proof 2 of this theorem is known that does not depend on the condition g > 0 (of course we can combine the proof for g>0 with the four color theorem to conclude that the result holds for all g, but it would be nice to have just one proof that works equally well for all g). Another thing we can study about graphs is what kind of walks exist in them. An eulerian walk , named after the great Swiss mathematician Leonhard Euler (1707-1783, pronounced Oiler), is one that uses every edge exactly once. A hamiltonian walk , named after the Irish mathematician Sir William Rowan Hamilton (1805-1865), is one that uses every vertex exactly once. Try to classify which graphs have such walks, with or without the condition that the starting and ending points must be the same (in the case of a hamiltonian walk the end vertex is thus counted twice and it is called a closed hamiltonian walk to distinguish from the open walk). This power question was barely an introduction to graph theory. It is a very broad field of mathematics, closely related to topology and knot theory. I hope you enjoyed this test, learned something from it, and that you will continue your studies of mathematics for many years. Edward Early 2/14/98