Very nice problem, Vasily turns out to be pretty good at drawing segments (well, labeling edges, really). Firstly, consider the obvious graph-theoretic interpretation of the problem: Reformulation wrote: Vasily has a simple graph $G(V,E)$ with $|V| = n$ and at each step labels an edge $e = \{u,v\}$ the minimal positive integer such that all other edges adjacent to $u$ or $v$ do not have this positive integer as a label. Find the maximal $k$ that Vasily can end up using as a label. Let $f(n)$ be the maximal $k$ that Vasily can achieve for a given $n \geq 4$, we will describe $f$ as follows: \[ f(n) = \begin{cases} 2n-4 \text{ even} \\ 2n-3 \text{ odd}. \end{cases} \] For this, we prove the following lemmas. Let $v_1, \cdots, v_n$ be the set of vertices in $G$. $\textbf{Lemma 1:}$ $f(n) \leq 2n-3$ for all $n \geq 5$ $\textbf{Proof)}$ If Vasily ever writes $t \geq 2n-2$ on an edge $e = \{v_i,v_j\}$, the other edges $\{v_i,v_k\}, \{v_j,v_l\}$ for $k,l \neq i,j$ of which there are $2n-4$ must contain $1, \cdots, 2n-3$ among them, which is a contradiction. $\blacksquare$ $\textbf{Lemma 2:}$ For $n$ odd, Vasily can indeed achieve $k = 2n-3$ which in turn means that $f(n) = 2n-3$ for $n$ odd. $\textbf{Proof)}$ Isolate vertex $v_1$ and take $G-v_1$, we have $n-1$ vertices which is even, now assume without loss of generality that the vertices $V-\{v_1\}$ form a regular even-gon. This is in order for us to be able to split the vertices $V-\{v_1\}$ into a set of disjoint perfect matchings. Notice that given this regular polygonal orientation of the vertices, Vasily may label each diameter a certain color $c_i$ for $i \in \{1, \cdots \frac{n-1}{2}\}$ and all other diagonals of $V-\{v_1\}$ perpendicular to this diameter. Then, Vasily firstly picks two of the perfect matchings that create the perimeter of the polygon and then picks each color $c_i$ in order, this then leads to $V-\{v_1\}$ containing each label $1, \cdots, n-2$ exactly $\frac{n-1}{2}$, more importantly, each vertex in $V-\{v_1\}$ contains each of the aforementioned labels once. Then, picking $\{v_1, v_i\}$ for $i \in \{2, \cdots, n\}$ in order, we must label $\{v_1, v_i\}$ with $n-3+i$ and in fact $\{v_1, v_n\}$ with $n-3+n = 2n-3$, as desired. $\blacksquare$ $\textbf{Lemma 3:}$ $f(n) \geq 2n-4$ for all even $n \geq 5$. $\textbf{Proof)}$ We again provide an explicit construction of Vasily's moves. Again construct the same disjoint union of perfect matchings on $V-\{v_1,v_2\}$ as in $\textbf{Lemma 2}$ using the fact that $n-2$ is even, then take $\{v_1, v_i\}$ for $i \geq 3$ which means that $\{v_1,v_i\}$ is labelled with $n-5+i$ for each $i \in \{1, \cdots, n\}$, then taking $\{v_2, v_i\}$ for $n-1 \geq i \geq 4$, $\{v_2,v_i\}$ is labelled with $n-6+i$ for all $i \in \{4, \cdots, n-1\}$, then taking $\{v_2,v_3\}$, Vasily labels it $2n-6$. Finally, $\{n-2, \cdots, 2n-6\}$ are the labels on $\{v_2, v_i\}$ for $i \in \{4, \cdots, n-1\}$ and $\{1, \cdots, n-3\} \cup \{2n-5\}$ are the labels of $\{v_j,v_n\}$ for $j \in \{1, 3,4, \cdots, n-1\}$ which means that $\{v_2,v_n\}$ is labeled $2n-4$, as desired. $\blacksquare$ $\textbf{Lemma 4:}$ $f(n) \leq 2n-4$ for all even $n \geq 5$. $\textbf{Proof)}$ Assume for the sake of contradiction that $f(n) > 2n-4$, then clearly $f(n) = 2n-3$ because $f(n) \leq 2n-3$ by $\textbf{Lemma 1}$. Assume without loss of generality that the largest labelled edge, that is, the edge with label $2n-3$ is the final labelling that Vasily performs on the edge between $\{v_i,v_j\}$. We have the following "anti claim" to finish off $\textbf{Lemma 4}$ and the problem. $\textbf{Claim:}$ There are disjoint edges adjacent to $v_i$ and $v_j$ labeled $1$ before the edge $\{v_i,v_j\}$ is labeled. $\textbf{Proof)}$ In fact, the set of edges labeled $1$ must form a perfect matching which implies the $\textbf{Claim}$. Assume for the sake of contradiction otherwise. Firstly, notice that the set of edges labelled $1$ must be a disjoint union of edges, assume that $E-\{v_i,v_j\}$ where we take $E$ to be the set of edges of $K_n$ has $\{v_{a_i},v_{b_i}\}$ as the edges labelled $1$ with $a_i \neq a_j, b_i \neq b_j, a_i \neq b_i$ for $i \neq j \in \{1, \cdots, t\}$ where $t < \frac{n}{2}$ because the set of edges labeled $1$ does not form a perfect matching of $G$. Then, consider $V - \{a_1,b_1, \cdots, a_t,b_t\}$ whose cardinality is at least $2$ and look at the induced subgraph formed by these vertices. As there are no edges labeled $1$ within these vertices, in fact only $v_i,v_j$ must be remaining, but then, as the last move Vasily would label $\{v_i,v_j\}$ as $1 < 2n-3$, this is ultimately a contradiction. $\blacksquare$ Now, notice that when Vasily labels $\{v_i,v_j\}$, by the above Claim, the set of labels adjacent to $v_i$ must be $\{1, x_1, \cdots, x_{n-3}\}$ and labels adjacent to $v_j$ must be $\{1, y_1, \cdots, y_{n-3}\}$ with $x_i \neq x_j, y_i \neq y_j, x_i \neq y_j$ for any $i,j \in \{1, \cdots, n-3\}$, then $|\{1, x_1, \cdots, x_{n-3}\} \cup \{1, y_1, \cdots, y_{n-3}\}| \leq 2n-5$ which means that the label of $\{v_i, v_j\}$ is at most $2n-4$, which is a contradiction. $\blacksquare$ Ultimately, $\textbf{Lemma 1, 2}$ prove that $f(n) = 2n-3$ for odd positive integers and $\textbf{Lemma 3,4}$ prove that $f(n) = 2n-4$ for even positive integers. $\blacksquare$