HMMT 二月 2018 · 冲刺赛 · 第 22 题
HMMT February 2018 — Guts Round — Problem 22
题目详情
- [ 12 ] How many graphs are there on 10 vertices labeled 1 , 2 , . . . , 10 such that there are exactly 23 edges and no triangles?
解析
- [ 12 ] How many graphs are there on 10 vertices labeled 1 , 2 , . . . , 10 such that there are exactly 23 edges and no triangles? Proposed by: Allen Liu Answer: 42840 Note that the sum of the degrees of the graph is 23 · 2 = 46, so at least one vertex has degree 5 or more. We casework on the maximal degree n . ( ) n Case 1: n ≥ 7, then none of the n neighbors can have an edge between each other, for edges 2 unusable, and the vertex with maximal degree cannot connect to the 9 − n other vertices. Then we ( ) ( ) n 10 have + 9 − n > − 23 = 22 when n ≥ 7, so there cannot be any graph in this case. 2 2 Case 2: n = 6. WLOG suppose that 1 is connected to 2 , 3 , 4 , 5 , 6 , 7, then none of 2 , 3 , 4 , 5 , 6 , 7 can connect to each other. Case 2.1: There is at least one edge between 8 , 9 , 10, then each of 2 , 3 , 4 , 5 , 6 , 7 can connect to at most ( ) 3 two of 8 , 9 , 10, for at most 6 · 2 + = 15 additional edges. Along with the 6 original edges, it is not 2 enough to each 23 edges. Case 2.2: There are no edges between 8 , 9 , 10, then this graph is a bipartite graph between 1 , 8 , 9 , 10 and 2 , 3 , 4 , 5 , 6 , 7. There can be at most 4 · 6 = 24 edges in this graph, so exactly one edge is removed ( ) 10 from this graph. There are · 24 = 5040 possible graphs in this case. 4 Case 3: n = 5. WLOG suppose that 1 is connected to 2 , 3 , 4 , 5 , 6, then none of 2 , 3 , 4 , 5 , 6 can connect to each other. Case 3.1: There is at least one edge between 7 , 8 , 9 , 10. Then each of 2 , 3 , 4 , 5 , 6 can connect to at most three of 7 , 8 , 9 , 10, for 5 · 3 = 15 edges. In this case at least three of 7 , 8 , 9 , 10 must not be connected to each other, so there can be at most three edges, for 5 + 15 + 3 = 23 edges at most. However, this requires the three disconnected vertices of 7 , 8 , 9 , 10 to be connected to all of 2 , 3 , 4 , 5 , 6 and the other vertex of 7 , 8 , 9 , 10, causing them to have degree 6. We can therefore ignore this case. (The case where 2 , 3 , 4 , 5 , 6 can connect to two or less of 7 , 8 , 9 , 10 can be easily ruled out.) Case 3.2: There are no edges between 7 , 8 , 9 , 10, then this graph is a bipartite graph between 1 , 7 , 8 , 9 , 10 ( ) ( ) 10 25 and 2 , 3 , 4 , 5 , 6. This is a K with two edges removed, which accounts for / 2 · = 126 · 300 = 5 , 5 5 2 37800 graphs. It is not difficult to see that Case 2.2 and Case 3.2 are disjoint (by considering max degree), so there are 5040 + 37800 = 42840 graphs in total.