PUMaC 2010 · 加试 · 第 8 题
PUMaC 2010 — Power Round — Problem 8
题目详情
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
解析
Problem 8.1. ( ★★★ , 12) For some 푛 ≥ 7, find a simple graph 퐺 with 푛 vertices, more than 6 푛 − 21 edges, and no 퐾 minor. 8 Answer: Start with 퐾 and delete 5 disjoint edges. This has 40 > 6(10) − 21 10 edges and is simple. If it had a 퐾 minor, then at most 2 of the sets 푓 ( 푣 ) contain 8 two vertices, so at least 6 of them contain only 1 vertex, so there’d be 6 vertices all adjacent to each other. But if we delete only 4 vertices of the graph, we delete endpoints of at most 4 of the removed edges, so both endpoints of one nonedge remain, contradiction. Hence there’s 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. 12