PUMaC 2010 · 加试 · 第 7 题
PUMaC 2010 — Power Round — Problem 7
题目详情
Problem 7.1. ( ★★ , 4) For each 푛 ≥ 6, construct a simple graph 퐺 with 푛 vertices, at least 5 푛 − 15 edges, and no 퐾 minor. 7 8 Credits
解析
Problem 7.1. ( ★★ , 4) For each 푛 ≥ 6, construct a simple graph 퐺 with 푛 vertices, at least 5 푛 − 15 edges, and no 퐾 minor. 7 Answer: Take a 퐾 , and 푛 − 5 vertices each adjacent only to the vertices of 5 that 퐾 . This has 5 푛 − 15 edges and is simple. If it had a 퐾 minor, then at 5 7 most 5 of the sets 푓 ( 푣 ) from the definition in Problem 2.2 would contain vertices from the original 퐾 , so at least 2 of them wouldn’t, but no two such sets are 5 adjacent. 8 Credits