How many graphs are there on 10 vertices labeled such that there are exactly 23 edges and no triangles?
Solution
Note that the sum of the degrees of the graph is , so at least one vertex has degree 5 or more. We casework on the maximal degree . Case 1: , then none of the neighbors can have an edge between each other, for edges unusable, and the vertex with maximal degree cannot connect to the other vertices. Then we have when , so there cannot be any graph in this case. Case 2: . WLOG suppose that 1 is connected to , then none of can connect to each other. Case 2.1: There is at least one edge between , then each of can connect to at most two of , for at most additional edges. Along with the 6 original edges, it is not enough to each 23 edges. Case 2.2: There are no edges between , then this graph is a bipartite graph between and . There can be at most edges in this graph, so exactly one edge is removed from this graph. There are possible graphs in this case. Case 3: . WLOG suppose that 1 is connected to , then none of can connect to each other. Case 3.1: There is at least one edge between . Then each of can connect to at most three of , for edges. In this case at least three of must not be connected to each other, so there can be at most three edges, for edges at most. However, this requires the three disconnected vertices of to be connected to all of and the other vertex of , causing them to have degree 6. We can therefore ignore this case. (The case where can connect to two or less of can be easily ruled out.) Case 3.2: There are no edges between , then this graph is a bipartite graph between and . This is a with two edges removed, which accounts for graphs. It is not difficult to see that Case 2.2 and Case 3.2 are disjoint (by considering max degree), so there are graphs in total.