返回题库

HMMT 二月 2018 · 冲刺赛 · 第 22 题

HMMT February 2018 — Guts Round — Problem 22

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 12 ] How many graphs are there on 10 vertices labeled 1 , 2 , . . . , 10 such that there are exactly 23 edgesand no triangles?
解析

英文解析

  1. [ 12 ] How many graphs are there on 10 vertices labeled 1 , 2 , . . . , 10 such that there are exactly 23 edgesand 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 ormore. We casework on the maximal degree n .
    ( )
    Case 1: n ≥ 7, then none of the n neighbors can have an edge between each other, for edgesnunusable, and the vertex with maximal degree cannot connect to the 9 − n other vertices. Then we 2
    ( ) ( )
    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 canconnect 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
    ( )
    two of 8 , 9 , 10, for at most 6 · 2 + = 15 additional edges. Along with the 6 original edges, it is not 3
    enough to each 23 edges.2
    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
    ( )
    from this graph. There are · 24 = 5040 possible graphs in this case.10
    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 4
    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 mostthree of 7 , 8 , 9 , 10, for 5 · 3 = 15 edges. In this case at least three of 7 , 8 , 9 , 10 must not be connectedto each other, so there can be at most three edges, for 5 + 15 + 3 = 23 edges at most. However, thisrequires the three disconnected vertices of 7 , 8 , 9 , 10 to be connected to all of 2 , 3 , 4 , 5 , 6 and the othervertex 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 thereare 5040 + 37800 = 42840 graphs in total.