PUMaC 2010 · 加试 · 第 3 题
PUMaC 2010 — Power Round — Problem 3
题目详情
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 3.3. ( ★ , 2) For each 푛 ≥ 2, find a graph 퐺 with 푛 vertices, more than 푛 − 1 edges, and no 퐾 minor. 3 Answer: For instance, 푛 disjoint loops. 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.)