PUMaC 2010 · 加试 · 第 1 题
PUMaC 2010 — Power Round — Problem 1
题目详情
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 1.3. ( ★★ , 4) Prove that a graph 퐺 is connected if and only if there’s a path between every pair of distinct vertices. Answer: We’ll prove that 퐺 is disconnected if and only if there exist distinct vertices 푢 and 푣 with no path between them. If there exist such vertices, let 퐴 ′ ′ be the set of vertices 푢 such that there’s a path from 푢 to 푢 , and let 퐵 be the remaining vertices. Then 푢 ∈ 퐴 and 푣 ∕ ∈ 퐴 by assumption, so both 퐴 and 퐵 are nonempty, and there are no edges between 퐴 and 퐵 because if there were ′ ′ an edge between 푢 ∈ 퐴 and 푣 ∈ 퐵 , then, since there’s a path between 푢 and ′ ′ ′ 푢 , there’d be a path between 푢 and 푣 , and 푣 would be in 퐴 , contradiction. Conversely, if 퐺 is disconnected, let ( 퐴, 퐵 ) be a partition of its vertices with no edges between 퐴 and 퐵 , and choose 푢 ∈ 퐴 and 푣 ∈ 퐵 . Then if there’s a path between them, its first vertex is in 퐴 and its last is in 퐵 , so some pair of adjacent vertices has one in 퐴 and the other in 퐵 , giving an edge between 퐴 and 퐵 , contradiction. Hence 퐺 is connected if and only if there’s a path between every pair of distinct vertices, as desired. 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 퐺 ∣ . 푉 ( 퐺 ) ∖{ 푣 } 3