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 anymap (e.g. a map of the United States) can be colored with four or fewer colors without giving neighboringregions (e.g. Massachusetts and New Hampshire) the same color. It was, until 22 years ago, one of themost famous unsolved problems in mathematics. The only known proof, however, is so long that itrequires a computer to carry it out. This power question will lead you through the basic definitions andtheorems of graph theory necessary to prove the Five Color Theorem, a weaker and much easier (thoughstill quite challenging) statement.
Part I - Graphs
Definitions: A graph is a collection of points and lines (or curves), calledvertices and edges , respectively, where each edge connects exactly twodistinct vertices and any two vertices are connected by at most one edge. Wesay that two vertices are adjacent if they are connected by an edge.
Notation: For this problem we will denote vertices by capital letters and theedge 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 bycapital 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 Ca . Which of the following are graphs? List the vertices and edges of each graphand explain why the others are not graphs. [1 point each]
i . A B iv . A B C
D C D Eii . v . B C
A B C Aiii . B vi . A B
A C E
Definition: Graph G is said to be isomorphic (from Greek roots meaning “same d cstructure”) to H , written G ≅ H , if the vertices of G can be given the names ofthe vertices of H in such a way that G and H have the same edges. Thisrelabling is called an isomorphism and is reversible, thus implying H ≅ G aswell.
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 toemphasize 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 explicitlylabled unless necessary. Thus to show two unlabled graphs are isomorphic wecan arbitrarily lable the vertices of one and then show that the other can belabled with the same names to yield the same edges.
c . For each of the following pairs of graphs, state whether or not they areisomorphic (you do not need to justify your answer). [parts i - iii are 1 pointeach, parts iv - vi are 3 points each]
i . iv .
and andii . v .
and andiii . vi .
and and
A couple more definitions are best given in this section, though there won’t beany questions specifically about them until later.
Definitions: A graph H is a subgraph of a graph G if every vertex of H is avertex 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 hasdegree 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 tographs with certain nice properties that we can exploit to prove cool theorems. So now we need onemore round of definitions, then the real fun begins!
Definitions: A graph is planar if it is isomorphic to a graph that has been drawnin a plane without edge crossings. Otherwise a graph is nonplanar. It shouldn’tbe 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 nin 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, orequivalently 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, itcuts 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 regionwhen counting).
W D Ea . 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 donot 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, andf 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, thenf ≤ e ≤ 3 v − 6 .3
d . Prove that the following graphs are nonplanar.2
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 toeach vertex in such a way that adjacent vertices have different colors.
The chromatic number χ (the Greek letter chi, pronounced like sky without thes) 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 grb ba . 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 graphobtained by taking the vertices of G and drawing edges only between thosethat 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 asubgraph of G (where the vertex V is only adjacent to the vertices shown).
V VV
V VVii . [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 onevertex (and all edges touching it) from G to obtain a graph with fewer verticeswhich also has χ >5 (you may use the Jordan Curve Theorem, which states thata closed loop that does not intersect itself divides the plane into an inside andoutside, and if a continuous curve joins a point on the inside to one on theoutside 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 pointsa. completely correct gets 1 point, total of 6 pointsi. yes. vertices A,B,C,D, edges AB,AC,AD,BDii. no. A and B are connected twiceiii. yes. vertices A,B,C, edges ABCiv. yes. vertices A,B,C,D,E, edges AB,AD,AE,BE,CD,CEv. no. the edge from B does not connect to another vertexvi. no. E is connected to itselfb. completely correct gets 1 point, total of 2 pointsi. BL,BE,BU,EL,EUii. A ↔ B, B ↔ L, C ↔ U, D ↔ Ec. 1 point each for i-iii, 3 for iv-vi, total of 12 pointsi. noii. noiii. noiv. yesv. novi. yesnote that the second graph in v has more vertices of degree 3 than the first
II. Planar Graphs, total of 60 pointsa. 1 point each for v, e, f, total of 6 pointsi. v=9, e=16, f=9
ii. v=7, e=14, f=9
note that v-e+f=2 by Euler’s formulab. 3 points each, total of 12 points note that this is a planar drawing of ii:
i. yesii. yesiii. noiv. yesfor iii, note that if we remove the two vertices of degree two and make the vertices theywere adjacent to adjacent to each other then we get a graph isomorphic to the one in d.ii.
c. total of 15 pointspartial 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 numberof edges bounding each faces and summing, then using the fact that we at most doublecounted [-2 for asserting we exactly double counted] each face we get 3 f ≤ 2 e, thusproving 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 toget v-e+f ≤ v-e+(2/3)e, thus by Euler’s formula 2 ≤ v-e/3, and rearranging yields the rightinequality.
d. 5 points for i, 10 for ii, total of 15 pointspartial 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 describedi. Assume it is planar. v=5, e=10, 3 v-6=9<e, contradicting c, thus nonplanarii. [1 point] Note that v=6, e=9, so 3 v-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 thegraph is planar, and that will provide the contradiction.
[2 points] Thus as in the proof of c we get 4 f ≤ 2 e.
[4 points] Hence f ≤ e/2, and again we want to eliminate f so adding v-e to both sides andapplying Euler’s formula yields 2 ≤ v-e/2. (or e ≤ 2 v-4)
[1 point] 6-9/2<2, contradicting the inequality just proved, thus the graph is not planar.
e. total of 12 pointspartial 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 hasdegree at least 6, then adding the degrees of each vertex double counts the edges so 6 v ≤
2 e.
[3 points] Now by c. e ≤ 3 v-6, and combining these inequalities we get 6 v ≤ 6 v-12, acontradiction, thus the graph must have at least one vertex of degree 5 or less.
III. Coloring, total of 56 pointsa. 3 points each, total of 12 pointsi. 4
ii. 5
iii. 4
iv. 3
b. total of 14 pointspartial 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 verticescolored with color 1. Then since no pair of them are adjacent, the are all adjacent in the 1
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 pointspartial credit: as described belowi. By II.e. G must have a vertex of degree 5 or lessii. [2 points] We want to remove the vertex V without decreasing the number ofcolors 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 withall vertices colored 1 or 3 then change the vertex colored 3 to 1, change any 1 verticesadjacent to it to 3, then change any 3 vertices adjacent to those to 1, and so on. Thisrecoloring does not affect any of the other vertices adjacent to V and thus allows us tomake 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 curveformed by the 1-3 walk and the edges from V to the vertices colored 1 and 3. The graph isplanar, 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 notconnected by a walk with all vertices colored 2 or 4, and by the previous argument we canchange the vertex colored 2 to 4 and make V color 2, so it can be removed withoutremoving the need for a sixth color.
iii. [4 points] We have shown that for any graph with χ >5 we can find one with fewervertices, and since the proof did not depend on the number of vertices we can keep doingthis 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-orderingprincipal 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. Heawoodfound 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 possiblesubgraphs it uses 1482. The way these theorems relate to coloring maps is that we canconsider 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 thefaces of the original graph in such a way that no two faces sharing an edge have the samecolor, which is what one does when coloring a map.
While it may seem that we used many definitions in this power question, there are manymore that had to be omitted. Some of the other interesting definitions used in graphtheory 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 connectthem arbitrarily to the other vertices. Kuratowski’s Theorem states that every nonplanargraph is a supergraph of an expansion of one of the two graphs in II.d. A corollary of thisis that a graph is nonplanar iff it is a supergraph of an expansion of one of those twographs, thus we can classify planar and nonplanar graphs in terms of just two particulargraphs.
A planar graph can alo be described as one that can be drawn on a sphere with no edgecrossings. A torus is essentially the surface of a solid sphere with a hole drilled all theway through it. The genus g of a graph is the minimum number of holes that must bedrilled in a sphere in order to be able to draw it without edge crossings. In other words agraph 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 + 48 g
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 cancombine the proof for g>0 with the four color theorem to conclude that the result holdsfor 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. Aneulerian walk , named after the great Swiss mathematician Leonhard Euler (1707-1783,
pronounced Oiler), is one that uses every edge exactly once. A hamiltonian walk , namedafter the Irish mathematician Sir William Rowan Hamilton (1805-1865), is one that usesevery vertex exactly once. Try to classify which graphs have such walks, with or withoutthe condition that the starting and ending points must be the same (in the case of ahamiltonian walk the end vertex is thus counted twice and it is called a closedhamiltonian walk to distinguish from the open walk).
This power question was barely an introduction to graph theory. It is a very broad field ofmathematics, 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 formany years.
Edward Early
2/14/98