PUMaC 2010 · 加试 · 第 9 题

PUMaC 2010 Power Round: Graph Minors These rules supersede any rules appearing elsewhere about the Power Test. For each problem, you may use without proof the results of all previous problems (that is, problems that appear earlier in the test), even if your team has not solved these problems. You may cite results from conjectures or subsequent problems only if your team solved them independently of the problem in which you wish to cite them. You may not cite parts of your proof of other problems: if you wish to use a lemma in multiple problems, reproduce it in each one. It is not necessary to do the problems in order, although it is a good idea to read all the problems, so that you know what is permissible to assume when doing each problem. However, please collate the solutions in order in your solution packet. Each section should start on a new page. Using printed and noninteractive online references, computer programs, cal- culators, and Mathematica (or similar programs), is allowed. (If you find some- thing online that you think trivializes part of the problem that wasn’t already trivial, let us know—you won’t lose points for it.) No communication with humans outside your team about the content of these problems is allowed. Each problem is marked with a number of stars. This is both the test-writers’ estimate of its relative difficulty and an indication of what sort of answer we expect: ★ problems need a short (probably one-sentence) explanation. The explanation should be just detailed enough that we couldn’t explain anything incorrect by it. ★★ problems need a proof. Partial credit will be given for ideas useful in a correct proof. ★ ★ ★ problems need a proof, and we reserve half their credit for the elegance of the proof. ★ ★ ★★ problems have the same rules as ★★ problems. ★ ★ ★ ★ ★ problems need an elegant proof. No points are awarded for an inelegant one. Note that giving an answer less rigorous than we expect is worth 0 points: for instance, if a problem asks you to find a graph with certain properties, giving the graph alone is worth nothing unless you also prove that it has those properties. Each problem also has a maximum possible score listed after its star rating. The total number of points available is 1,000,100. Power test scores will be scaled before use in the rest of PUMaC. 1

1 Basic definitions Definition 1.1. A multiset is a set in which repeated elements are allowed. The order of the elements does not matter, but the multiplicities do. Definition 1.2. A graph 퐺 is a multiset 퐸 ( 퐺 ) of submultisets (“edges”) of size 2 of a set 푉 ( 퐺 ) (“vertices”). For instance, {{ 1 , 1 } , { 1 , 1 } , { 1 , 3 } , { 1 , 3 } , { 2 , 3 } , { 4 , 5 }} is a nonsimple graph on 5 vertices 1, 2, 3, 4, and 5. For ease of use, we often draw pictures of graphs with the vertices as dots and the edges as line segments connecting them, and say that two vertices are adjacent if they’re both elements of some edge. For instance, the following are two pictures of 퐾 : 4 You can use these pictures to represent graphs wherever they occur, but keep in mind that a graph is defined by sets of vertices and edges, not by its drawings. Two equal edges of a graph are called parallel edges , and an edge with two equal vertices is called a loop . Definition 1.3. The simplification of a graph 퐺 is the graph 퐻 with all loops removed, and all but one of each set of parallel edges removed. A graph is simple if it has no loops or parallel edges. Here are drawings of the most basic graphs that are not simple: A few special types of graphs deserve mention: ∙ A complete graph 퐾 is the simple graph on 푛 vertices, every pair of which 푛 are adjacent. 2

∙ A complete bipartite graph on 푚 and 푛 vertices 퐾 is the simple graph 푚,푛 with 푚 + 푛 vertices, with each of the first 푚 vertices adjacent to each of the last 푛 (for a total of 푚푛 edges). ∙ A cycle 퐶 has 푛 vertices 푣 , . . . , 푣 , an edge { 푣 , 푣 } for each 1 ≤ 푖 < 푛 , 푛 1 푛 푖 푖 +1 and an edge { 푣 , 푣 } . So for all 푛 , 퐶 has 푛 edges. 1 푛 푛 ∙ A wheel 푊 is 퐶 plus an extra vertex adjacent to all the vertices of 퐶 푛 푛 푛 (by one edge). Definition 1.4. A graph 퐺 is disconnected if and only if its vertices can be divided into two nonempty sets 퐴 and 퐵 such that no vertex of 퐴 is adjacent to any vertex of 퐵 . Otherwise, 퐺 is connected . Definition 1.5. A path between two vertices 푢 and 푣 is a sequence of distinct vertices 푣 = 푢, 푣 , . . . , 푣 = 푣 such that for every 0 ≤ 푖 < 푘 , 푣 is adjacent to 0 1 푘 푖 푣 . The length of such a path is 푘 , the number of edges. 푖 +1 Problem 1.1. ( ★ , 2) For which values of 푛 is 퐶 simple? 푛 Problem 1.2. ( ★ , 1) How many edges does 푊 have? 6 Problem 1.3. ( ★★ , 4) Prove that a graph 퐺 is connected if and only if there’s a path between every pair of distinct vertices. Definition 1.6. If 퐺 is a graph and 퐴 is a subset of its vertices, then the subgraph of 퐺 induced on 퐴 , denoted 퐺 ∣ , is the graph whose vertex set is 퐴 퐴 such that for any 푢, 푣 ∈ 퐴, the multiplicity of the edge { 푢, 푣 } in 퐸 ( 퐺 ∣ ) is the 퐴 same as the multiplicity of { 푢, 푣 } in 퐸 ( 퐺 ). Definition 1.7. If 퐺 is a graph and 푣 ∈ 푉 ( 퐺 ), then 퐺 ∖ 푣 (“ 퐺 delete 푣 ”) is 퐺 ∣ . 푉 ( 퐺 ) ∖{ 푣 } Problem 1.4. ( ★ , 1) What graph do you get by deleting a vertex of 퐾 ? 푛 Problem 1.5. ( ★ , 4) How many distinct graphs can you get by deleting three vertices of 푊 ? Note that, say, two copies of 퐾 aren’t distinct, even if they 2010 3 came from different vertices of a bigger graph. Definition 1.8. If 퐺 is a graph and 푒 ∈ 퐸 ( 퐺 ), then 퐺 ∖ 푒 (“ 퐺 delete 푒 ”) is the graph with the same vertices as 퐺 , and the same multiset of edges except we remove one copy of 푒 . Definition 1.9. A graph 퐻 is a subgraph of a graph 퐺 if you can get from 퐺 to 퐻 by deleting vertices (i.e., taking an induced subgraph) and then deleting edges. Problem 1.6. ( ★ , 1) Prove that if a graph 퐺 with 푛 ≥ 0 vertices doesn’t have 퐾 as a subgraph, then it has at most − 푛 edges. 1 3

2 Edge contraction Definition 2.1. If 퐺 is a graph and 푒 = { 푢, 푣 } ∈ 푉 ( 퐺 ) (with 푢 and 푣 not necessarily distinct), then 퐺/푒 (” 퐺 contract 푒 ”) is the subgraph of 퐺 induced on all its vertices but 푢 and 푣 , plus an extra vertex 휖 , and some new edges containing 휖 : each edge of 퐺 of the form { 푢, 푎 } or { 푣, 푎 } , for 푎 ∕ ∈ { 푢, 푣 } is replaced with an edge { 휖, 푎 } . Each edge of 퐺 of the form { 푢, 푣 } , { 푢, 푢 } , or { 푣, 푣 } , is replaced with a loop at 휖 , except for 푒 itself. To picture this, you can imagine that the vertices are big blobs of clay and each edge is a thin cable connecting two blobs. When you contract an edge, you mold the cable and the two blobs it connected into one new blob, without destroying the other cables. For example, if you contract an edge of 퐾 , you 5 get 퐾 plus one other vertex sharing two edges with each vertex in 퐾 . If you 3 3 contract an edge of 퐾 you get 푊 . 3 , 3 4 Problem 2.1. ( ★ , 2) ∙ True or false: You can contract an edge of 푊 to get 푊 . 4 3 ∙ True or false: If an edge 푒 is a loop (that is, it’s { 푣, 푣 } for some vertex 푣 ), then 퐺/푒 = 퐺 ∖ 푒 . Definition 2.2. A graph 퐻 is a minor of a graph 퐺 if and only if you can “reach 퐻 from 퐺 by repeatedly deleting a vertex, deleting an edge, or con- tracting an edge.” That is, if and only if there’s a sequence of graphs 퐺 = 0 퐻, 퐺 , 퐺 , . . . , 퐺 , 퐺 = 퐺 such that for each 푖 such that 0 ≤ 푖 < 푘 , either 1 2 푘 − 1 푘 퐺 = 퐺 ∖ 푣 for some vertex 푣 , or 퐺 = 퐺 ∖ 푒 for some edge 푒 , or 퐺 = 퐺 /푒 푖 푖 +1 푖 푖 +1 푖 푖 +1 for some edge 푒 . Problem 2.2. ( ★★ , 6) Prove that 퐻 is a minor of 퐺 if and only if you can map each vertex 푣 ∈ 푉 ( 퐻 ) to a nonempty subset of 퐺 ’s vertices 푓 ( 푣 ) ⊂ 푉 ( 퐺 ) such that: ∙ For all 푣 ∈ 푉 ( 퐻 ), the subgraph of 퐺 induced on 푓 ( 푣 ) is connected. ∙ For all 푢, 푣 ∈ 푉 ( 퐻 ) with 푢 ∕ = 푣 , 푓 ( 푢 ) ∩ 푓 ( 푣 ) = {} . ∙ For all 푢, 푣 ∈ 푉 ( 퐻 ), ∣ 퐸 ( 푓 ( 푢 ) , 푓 ( 푣 )) ∣ − ∣ 푓 ( 푢 ) ∩ 푓 ( 푣 ) ∣ ≥ 퐸 ( { 푢 } , { 푣 } ) − ∣{ 푢 } ∩ { 푣 }∣ , where 퐸 ( 푋, 푌 ) is the number of edges with one endpoint in 푋 and the other in 푌 . Problem 2.3. ( ★ , 3) ∙ Is 퐾 a minor of 퐾 ? 5 8 ∙ Is 퐾 a minor of 퐾 ? 5 2 , 2 ∙ Is 퐾 a minor of 퐾 ? 5 3 , 3 ∙ Is 퐾 a minor of 퐾 ? 5 4 , 4 4

∙ Is 퐾 a minor of 퐾 ? 5 5 , 5 ∙ Is 퐾 a minor of 퐶 ? 5 125 ∙ Is 퐾 a minor of 푊 ? 4 3 ∙ Is 퐾 a minor of 푊 ? 4 5 ∙ Is 퐾 a minor of 푊 ? 5 6 Problem 2.4. ( ★ , 2 points) ∙ What is the smallest 푛 such that 퐾 is a minor of 퐾 ? 2010 푛,푛 ∙ What is the smallest 푛 such that 푊 is a minor of 퐾 ? 2010 푛,푛 Problem 2.5. ( ★ , 1) Prove that if a simple graph 퐺 with 푛 ≥ 1 vertices has no 퐾 minor, then it has at most 0 edges. 2 3 Graph colorings Definition 3.1. A graph is 푘 -colorable if and only if you can partition its vertices into 푘 (possibly empty) subsets such that no vertices within a subset are adjacent. (Intuitively, the subsets are colors, and no two vertices of the same color are adjacent.) Problem 3.1. ( ★ , 1) Find a graph that’s not 3-colorable. Hadwiger’s conjecture states that if 퐺 is a simple graph with no 퐾 minor, 푡 then 퐺 is ( 푡 − 1)-colorable. Problem 3.2. ( ★★ , 4) Prove Hadwiger’s conjecture for 푡 = 3. Problem 3.3. ( ★ , 2) For each 푛 ≥ 2, find a graph 퐺 with 푛 vertices, more than 푛 − 1 edges, and no 퐾 minor. 3 4 Planar graphs Definition 4.1. A graph is planar if and only if it can be drawn in the plane with no two edges intersecting. (Edges needn’t be straight lines, although it happens that every simple planar graph can be drawn with straight-line edges and no edges intersecting.) Problem 4.1. ( ★ , 3) Which of the following graphs are planar? ∙ 퐾 4 ∙ 퐶 4 ∙ 푊 4 5

∙ 퐾 4 , 4 ∙ Problem 4.2. ( ★ ★ ★ ★ ★ , 1,000,000) Prove that every loopless planar graph is 4-colorable. (This is called the Four-color theorem ). Problem 4.3. ( ★★ , 4) Prove that if a simple graph 퐺 with 푛 ≥ 3 vertices has no 퐾 minor, then it has at most 2 푛 − 3 edges. 4 5 Excluded Minor Theorems Problem 5.1. ( ★★ , 4) Prove that 퐾 and 퐾 are not planar. 5 3 , 3 Problem 5.2. ( ★★ , 2) Prove that if 퐺 has a 퐾 or 퐾 minor, then 퐺 isn’t 5 3 , 3 planar. A famous theorem of Wagner’s (sometimes attributed to Kuratowski, al- though he actually proved something else) states that a graph is planar if and only if it has no 퐾 minor and no 퐾 minor. The other direction of the proof 5 3 , 3 is easily googleable, if you’re curious. Many classic types of graphs can be described easily in terms of minors that they don’t have. For instance: ∙ Graphs that don’t have 퐶 (that is, the one-vertex, one-edge graph) as a 1 minor are forests. ∙ Graphs that don’t have 퐶 as a minor are forests with loops allowed. 2 ∙ Graphs that don’t have 퐶 as a minor are forests with loops and parallel 3 edges allowed. ∙ Graphs that don’t have a path of length 2 as a minor are matchings (plus isolated vertices, loops, and parallel edges). Problem 5.3. ( ★★ , 4) What graphs don’t have a path of length 3 as a minor? Definition 5.1. A 푘 -sum of two simple graphs 퐺 and 퐻 takes a 퐾 subgraph 푘 of each one, identifies the vertices in them (that is, glues the 퐾 s together), and 푘 deletes the edges of the 퐾 . For instance, a 3-sum of two 퐾 s is 퐾 . 푘 4 2 , 3 6

Problem 5.4. ( ★ , 2) How many distinct graphs can you get as 2-sum of 퐾 2 , 3 and 푊 ? 4 Problem 5.5. ( ★★ , 4) Prove that if simple 퐺 and 퐻 don’t have 퐾 as a minor, 3 , 3 then no 0-sum, 1-sum, or 2-sum of 퐺 and 퐻 has 퐾 as a minor. 3 , 3 Problem 5.6. ( ★★ , 2) Is the same true for 3-sums? Problem 5.7. ( ★ ★ ★ , 8) Prove that if a simple graph 퐺 with 푛 ≥ 4 vertices has no 퐾 minor, then it has at most 3 푛 − 6 edges. 5 6 Reminder Problem 6.1. (, 1) On every page you submit, put your team’s name, a page count, and solutions to problems from at most one section. Problem 6.2. ( ★ ★ ★★ , 16) Prove that if a simple graph 퐺 with 푛 ≥ 5 vertices has no 퐾 minor, then it has at most 4 푛 − 10 edges. 6 7 The End. Problem 7.1. ( ★★ , 4) For each 푛 ≥ 6, construct a simple graph 퐺 with 푛 vertices, at least 5 푛 − 15 edges, and no 퐾 minor. 7 8 Credits Problem 8.1. ( ★★★ , 12) For some 푛 ≥ 7, find a simple graph 퐺 with 푛 vertices, more than 6 푛 − 21 edges, and no 퐾 minor. 8 Thanks to Adam Hesterberg for writing the Power Round and Ian Frankel and Paul Seymour for editing it. Thanks in advance to the graders. 7