, 2018

Solution:

Note that the sum of the degrees of the graph is $23 \cdot 2 = 46$, so at least one vertex has degree $5$ or more. We casework on the maximal degree $n$.

Case 1: $n \geq 7$, then none of the $n$ neighbors can have an edge between each other, for $\binom{n}{2}$ edges unusable, and the vertex with maximal degree cannot connect to the $9-n$ other vertices. Then we have $\binom{n}{2} + 9 - n > \binom{10}{2} - 23 = 22$ when $n \geq 7$, so there cannot be any graph in this case.

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 two of $8,9,10$, for at most $6 \cdot 2 + \binom{3}{2} = 15$ additional edges. Along with the $6$ original edges, it is not enough to reach $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 \cdot 6 = 24$ edges in this graph, so exactly one edge is removed from this graph. There are $\binom{10}{4} \cdot 24 = 5040$ possible graphs in this case.

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 \cdot 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$ and $2,3,4,5,6$. This is a $K_{5,5}$ with two edges removed, which accounts for $\binom{10}{5} / 2 \cdot \binom{25}{2} = 126 \cdot 300 = 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.