45th Mongolian Mathematical Olympiad

Suppose that such $45$ vertices do not exist. If removal of any one of the edges does not interfere with this condition, then remove this edge. Repeating this action until there are no longer any edges to be removed results in the graph such that after a removal of any arbitrary edge, $45$ vertices that represent the remaining edges can be selected but $45$ vertices that represent all of the edges cannot be selected. Suppose that edges of this graph are $e_1,e_2,\dots ,e_m$. Then for each removal of $e_i$, those that intersect with every other edge except $e_i$, there exists a set such that $v_i\in G(v)$, $|v_i|=45$. In other words, when $e_i\cap v_i=\varnothing$ and $i\ne j$, then $e_i\cap v_j=\varnothing$.

Consider $\pi$ combination $v(g)=\{1,2,\dots ,n\}$ of number $1,2,\dots ,n$. In case of this combination, if the two vertices of $e_i$ edge is located before all the vertices of set $v_i$, then let $\pi$ be called $i$th type combination. If $i\ne j$, show that $\pi$ combination cannot at the same time be $i$th and $j$th type. Suppose that for $\pi$ combination, the last vertices of the $e_i$ edge is located on the $k$th position, after the last vertices of the $e_j$ edge. Since $\pi$ is of $i$th type, all of vertices in set $v_i$ is located after $k$. On the other hand, since vertices $v\in e_j\cap v_i\ne \varnothing$ belongs to $e_j$, it must be located before $k$. Hence there is a contradiction. Therefore, each combination must belong to only one type.

On the other hand, since the number of $i$th type combination is $C_n^{47}2!45!$ and the total number of combinations is $n!$, $C_n^{47}m\cdot 2!45!(n-47)!\le n!$. From here it follows that $m\le C_{47}^2<1100$ and thus, given the conditions of the problem, there is a contradiction. Therefore $45$ vertices that represent all the edges can be selected/found.