PUMaC 2010 · 加试 · 第 6 题

Problem 6.2. ( ★ ★ ★★ , 16) Prove that if a simple graph 퐺 with 푛 ≥ 5 vertices has no 퐾 minor, then it has at most 4 푛 − 10 edges. 6 Answer: As in the previous section’s final problem, let 퐺 be a counterexam- ple with ∣ 푉 ( 퐺 ) ∣ + ∣ 퐸 ( 퐺 ) ∣ minimal. If 퐺 has only 5 vertices, then it has at most 10 ≤ 4(5) − 10 edges. If it has any vertices of degree 0, 1, 2, 3, or 4, they can be deleted. If it has a vertex 푣 of degree 5, not all its neighbors are adjacent, so one of them, 푢 , is adjacent to at most 3 of 푣 ’s neighbors; by deleting those at most 3 edges and contracting { 푢, 푣 } , we get a smaller counterexample. If there’s a vertex of degree 6 one of whose neighbors is adjacent to at most 3 others, then we can delete and contract similarly. If there’s a vertex of degree 6 all of whose neighbors ( 푢 , 푢 , 푢 , 푢 , 푢 , and 푢 ) are adjacent to at least 4 others, that is, 1 2 3 4 5 6 푣 and its neighbors have at least these edges: If there’s a path between any of the three pairs of vertices not shown to be adjacent here (say { 푢 , 푢 } , { 푢 , 푢 } , and { 푢 , 푢 } , then contracting it down to 1 4 2 5 3 6 an edge and contracting one more edge gives a 퐾 minor, as in the previous 6 problem. The new idea we introduce for this solution is a complete cutset of the graph: a subset of vertices that’s complete (each vertex is adjacent to each other one) and a cutset (its removal disconnects the graph). For instance, in the case in progress (with a vertex of size 6), three mutually adjacent neighbors of 푣 (say, the rightmost three in the picture, or { 푢 , 푢 , 푢 } ) are a clique cutset of size 4 5 6 3: they’re all adjacent to each other, and removing them disconnects the graph since there’s no path between some other neighbor 푤 of 푢 (which exists because 4 푢 has degree at least 6) and 푢 . 4 1 If there’s a clique cutset 퐶 ⊂ 푉 ( 퐺 ) of size 3, and 퐴 and 푉 ( 퐺 ) ∖ ( 퐴 ∪ 퐶 ) are nonempty subsets of 푉 ( 퐺 ) with no edges between them, then 퐺 ∣ and 퐴 ∪ 퐶 퐺 ∣ are each smaller graphs with no 퐾 minor, so they have at most 푉 ( 퐺 ) ∖ 퐴 6 4( ∣ 퐴 ∣ + ∣ 퐶 ∣ ) − 10 and 4( ∣ 푉 ( 퐺 ) ∣ − ∣ 퐴 ∣ ) − 10 edges, respectively. Hence the total number of edges in the graph is at most 4( ∣ 퐶 ∣ ) − 10+4( ∣ 푉 ( 퐺 ) ∣ ) − 10 = 4 ∣ 푉 ( 퐺 ) ∣− 8, but this double-counts the three edges in 퐶 , for a total of at most 4 푛 − 11 edges in 퐺 . So, 퐺 has no vertex of degree 6. So, every vertex of 퐺 has degree at least 7. Also, if every vertex of 퐺 has degree at least 8, then there’d be at least 4 푛 edges, and we could delete some to get a smaller counterexample. So 퐺 has some vertex 푣 of degree 7. Each of 푣 ’s neighbors is adjacent to at least 4 others, or we could contract to get a smaller counterexample as above. We claim that 푣 ’s neighbors contain a 퐾 minor (so 5 퐺 contains a 퐾 ). Indeed, the missing edges are either a subset of 퐶 , a subset 6 7 of 퐶 , a subset of 퐶 plus a disjoint edge, a subset of a disjoint union of a 퐶 6 5 4 and a 퐶 , or a subset of 퐶 plus two disjoint edges, but in all these cases there’s 3 3 11 a 퐾 minor of the neighbors, and hence a 퐾 minor of 퐺 , contradiction. 5 6 7 The End.