PUMaC 2010 · 加试 · 第 5 题
PUMaC 2010 — Power Round — Problem 5
题目详情
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.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 Answer: Suppose for contradiction that a 0-sum, 1-sum, or 2-sum of graphs 퐺 and 퐻 with no 퐾 minor has a 퐾 minor. Let 퐶 (of size at most 2) be 3 , 3 3 , 3 ′ the 푘 -vertex subset of the sum where the 퐾 s were glued together, and let 퐺 푘 ′ and 퐻 be the remainders of 퐺 and 퐻 in the sum. 9 We claim that at least one of the sets 푓 ( 푣 ) from the definition in Problem 2.2 ′ is contained in 퐻 . Suppose not; then we’ll show that 퐺 has a 퐾 minor. For 3 , 3 ′ any 푣 ∈ 퐾 for which the set 푓 ( 푣 ) ∈ 퐺 + 퐻 doesn’t intersect 퐻 , choose the 3 , 3 ′ same set 푓 ( 푣 ) in 퐺 ; for any 푣 for which 푓 ( 푣 ) intersects 퐻 (but isn’t contained ′ in it, by assumption), it intersects 퐶 ; restrict that set to 퐺 ∪ 퐶 . Then all the conditions for 퐺 to have a 퐾 minor in Problem 2.2 are satisfied except 3 , 3 ′ possibly adjacency between the vertices 푣 such that 푓 ( 푣 ) intersected 퐻 , but for every such 푣 , 푓 ( 푣 ) contains a vertex in 퐶 , and all the vertices of 퐶 are adjacent in 퐺 . So 퐺 has a 퐾 minor, contradicting the assumption that none of the 3 , 3 ′ sets 푓 ( 푣 ) from the definition of Problem 2.2 is contained in 퐻 . Similarly, at least one of the sets 푓 ( 푣 ) from the definition in Problem 2.2 is ′ contained in 퐺 Delete the (at most two) vertices in 퐶 , and the (at most two) vertices 푣 of 퐾 such that 푓 ( 푣 ) contained a vertex in 퐶 . This disconnects 퐺 + 퐻 , and by 3 , 3 the first part of this proof there’s a set 푓 ( 푣 ) on each side of the disconnect, so it disconnects 퐾 . But there are no two vertices of 퐾 such that deleting them 3 , 3 3 , 3 disconnects 퐾 , contradiction. Hence 퐺 + 퐻 has no 퐾 minor, as desired. 3 , 3 3 , 3