10.4. Given a natural number $n>4$. On the plane, $n$ points are marked, no three of which lie on the same line. Vasily draws all segments connecting pairs of marked points, one by one. At each step, while drawing the next segment $S$, Vasily marks it with the smallest natural number that has not yet been used to mark any segment sharing an endpoint with $S$. For what largest $k$ can Vasily act in such a way that some segment is marked with the number $k ? \quad$ (A. Glebov, D. Khramiov)
Answer. $k=2 n-3$ for odd $n$, and $k=2 n-4$ for even $n>4$.

Solution. Estimation. Consider the step at which Vasily marks some segment $A B$. Before this step, from each of the points $A$ and $B$, there are at most $n-2$ segments, and they contain at most $2 n-4$ different marks. Therefore, Vasily can definitely mark this segment with a number not exceeding $2 n-3$. Thus, $k \leqslant 2 n-3$.

If $n$ is even, this estimate can be refined as follows. We will call a segment marked with a one a small segment. We will prove that at the end of the process, a small segment will exit from each point; assume the opposite. The points from which small segments exit can be paired with points connected by such a segment. Therefore, there are at least two points $X$ and $Y$ from which no small segments exit. It follows that when Vasily drew the segment $X Y$, he should have marked it with a one - a contradiction.

Thus, if the segment $A B$ is not small, then at the end of the process, among the segments exiting from $A$ and $B$, besides $A B$, there will be two small segments. Therefore, on these segments, there will be at most $2(n-2)-1=2 n-5$ different marks. Consequently, when Vasily draws the segment $A B$, he can mark it with a number not exceeding $2 n-4$, and $k \leqslant 2 n-4$.

Example. It remains to prove that Vasily can achieve the specified values of $k$.

Lemma. If the number of points is even and equal to $m$, then Vasily can mark all segments between these points using only numbers from 1 to $m-1$. Moreover, from each point, segments marked with all these numbers will exit.

Proof. The statement of the lemma does not depend on the specific arrangement of the points, so we can assume that $m-1$ points $A_{1}, \ldots, A_{m-1}$ are located at the vertices of a regular $(m-1)$-gon, and the remaining point is at its center $O$.

Then all segments between these points can be divided into $m-1$ sets $S_{1}, S_{2}, \ldots, S_{m-1}$ such that the segments of one set do not have common endpoints. For example, in the set $S_{i}$, we can include the segment $O A_{i}$ and all segments connecting pairs of vertices of the $(m-1)$-gon and perpendicular to $O A_{i}$. From each point, there is one segment from each set.

Now Vasily can first mark all segments of the set $S_{1}$ with the number 1, then all segments of the second set with the number 2, and so on.

Returning to the solution. Let $n$ be odd, and let $A$ be the marked point. Suppose Vasily first marks all segments between points other than $A$ with numbers from 1 to $n-2$ according to the lemma. Then he draws all $n-1$ segments from $A$; each segment $A B$ he will have to mark with a number greater than $n-2$, because from $B$ there are already segments marked with all smaller numbers. Moreover, all these $n-1$ segments will be marked with different numbers, because they have a common endpoint. Therefore, they will be marked with the numbers $n-1, n, \ldots, 2 n-3$, that is, Vasily will get a mark $k=2 n-3$.

Now let $n$ be even. Choose two marked points $A$ and $B$; let $C_{1}, C_{2}, \ldots, C_{n-2}$ be the other marked points. Suppose Vasily first marks all segments between the points $C_{i}$ with numbers from 1 to $n-3$ according to the lemma, and also marks the segment $A B$ with the number 1. Then he sequentially draws the segments $A C_{1}$, $A C_{2}, \ldots, A C_{n-3}$; since the vertices $C_{i}$ already have segments with marks from 1 to $n-3$, the new segments will be marked with the numbers $n-2, n-1, \ldots, 2 n-6$ respectively. Next, Vasily draws the segments $B C_{n-3}, B C_{2}, B C_{3}, \ldots, B C_{n-4}$; similarly, he will mark them with the numbers $n-2, n-1, \ldots, 2 n-6$ respectively.

Now in the vertices $A$ and $B$, there are already segments with all marks from $n-2$ to $2 n-6$, and in the vertex $C_{n-2}$, there are segments with all marks from 1 to $n-3$. Therefore, when Vasily draws the segments $A C_{n-2}$ and $B C_{n-2}$, the first will be marked with the number $2 n-5$, and the second with the number $2 n-4$ (because it has a common endpoint with the previous one). Therefore, Vasily has achieved the appearance of the number $k=2 n-4$.
$\leqslant 3$ points. In the case analysis of what the second largest main divisor can be, at least one case is considered incorrectly.

$\leqslant 1$ point. In the work, it is assumed that both main divisors are the original number divided by some of its prime divisors.

$\leqslant 2$ points. In the work, it is assumed that either the main divisors are the original number divided by some of its prime divisors, or the original number is a power of a prime number.