PUMaC 2010 · 加试 · 第 4 题

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 Answer: Suppose not, so there’s at least one such graph 퐺 . Let 퐺 be such a graph with ∣ 푉 ( 퐺 ) ∣ + ∣ 퐸 ( 퐺 ) ∣ (the sum of the number of vertices of 퐺 , ∣ 푉 ( 퐺 ) ∣ , and the number of edges of 퐺 , ∣ 퐸 ( 퐺 ) ∣ ) minimal. If 퐺 has only 3 vertices, then it has at most 3 ≤ 2(3) − 3 edges. If 퐺 (with ∣ 푉 ( 퐺 ) ∣ > 3) has any vertices of degree 0, 1, or 2, deleting them gives a graph with 푛 − 1 ≥ 3 vertices and more than (2 푛 − 3) − 2 = 2( 푛 − 1) − 3 edges, contradicting the minimality of 퐺 . If 퐺 has a vertex 푣 of degree at most 3, not all of its neighbors are adjacent, or we’d have a 퐾 subgraph. So, one of its neighbors, 푢 , is adjacent to at most 1 other. 4 Delete that edge, if it exists, and contract the edge { 푢, 푣 } ; that gives another simple graph with 푛 − 1 vertices and more than (2 푛 − 3) − 2 edges, contradicting the minimality of 퐺 . So every vertex of 퐺 has degree at least 4. But then 퐺 has at least 2 푛 edges, and we can delete any of them to get a get a smaller simple graph with no 퐾 minor and at least 2 푛 − 3 edges. Hence no such 퐺 exists, as 4 desired. 5 Excluded Minor Theorems