Is this ISL?

No, its not

@below thank you for the correction

@above i believe your argument for n odd is mistaken; you've used 2k-5+4+3=2k+2 vertices. And intuitively, the total degree of all vertices should be even, so if an odd number of vertices all have odd degree something should be wrong...

navi_09220114 wrote: No, its not Ok, Thank you

The answer is all odd $n$ In fact, we can go a step further and show that : $(1)$ In a non-trivial network, the network is versatile iff it has at least one vertex of even degree $(2)$ Also, in a non-trivial network with all degrees odd, the permutations which can be reached are precisely the even permutations. To prove the only if part of $(1)$, just note that odd cycles are even permutations so in a graph with all degrees odd you cannot reach any odd permutation. The main idea to prove the if part of $(1)$ is to induct on the number of non-leaves with the base case of 2 non-leaves being the most crucial case. The proof of $(2)$ is pretty similar.

Official Solution: Answer. All odd $n$. Solution.We interpret the network as a tree and root it at an arbitrary vertex. For a permutation $p_1,p_2,\cdots,p_n$ of $\{1,2,\cdots,n\}$, we say that it is even if it can be transformed into the identity permutation with an even number of transpositions and even otherwise (it is well-known that this is well-defined, and can be proven from scratch by considering the parity of the number of cycles in the graph $i \rightarrow p_i$). Fix any target labeling of edges in the tree. Then, we say that our current labeling is even if we can transform it into the target labeling by an even number of label swaps (where we are allowed to swap any two labels). Call the labeling odd otherwise. Assume that our network is nontrivial. The key claim is that the current labeling cannot reach the target labeling using a finite number of spins if and only if $\bullet$ All vertices have odd degree. $\bullet$ The current labeling of edges is odd. Note that this claim implies the result, because if a nontrivial network is not versatile, then it must have an even number of vertices (or else the sum of degree is odd) and for any even $n \ge 6$, we can construct a nonversatile nontrivial network by taking a tree where the root has $n-3$ children, and one of its children has $2$ children. It is impossible to swap exactly one pair of labels in the network. Hence, it remains to prove the claim. Firstly, we prove that if the conditions are satisfied, then the target labeling can never be reached. Indeed, it is sufficient to note that since every vertex has odd degree, every spin is equivalent to some even number of transpositions. Thus, the parity of the network is always preserved after a spin. This implies that we can never reach the target labeling using spins, since we begin with an odd labeling. Now, we prove that every labeling of a nontrivial network that does not satisfy both conditions can be transformed into the target labeling using spins. We will use induction on $n$, with the base case $n=4$ being trivial because the only valid nontrivial network is isomorphic to a path, and we can swap any two adjacent labels in a path (which allows us to reach any permutation of labels). Suppose our statement holds for all smaller $n$. Let $r$ be the root of the current tree and $c_1,c_2,\cdots,c_k$ be the children of $r$ (from left to right). Define $S_i$ as the induced subgraph formed by $r$ and the vertices in the subtree of $c_i$. Our proof proceeds in several steps. Step 1: Make $S_i$ contain only edge labels that belong to $S_i$ in the target labeling. Let $m$ be the number of edge labels that are currently in the wrong subtree, i.e. the number of edges which are currently in $S_i$ for some $i$ with its label in $S_j$ for some $j \neq i$ in the target labeling. We will show that if $m>0$, then there exists a sequence of spins that decreases $m$ (which will imply that we can perform this step). Choose an edge $e \in S_i$ such that its current label $l_e$ belongs in another subtree $S_j$ in the target labeling. Choose any label $l_f$ that is currently on some edge $f \in S_j$ but does not belong in $S_j$ in the target labeling (it must exist because $S_j$ does not contain all its target labels yet). We will move $l_e$ to $S_j$ and $l_f$ to $S_i$ while ensuring that every other label stays in its subtree. Clearly, this operation would decrease $m$. We will state this operation as the following lemma. Lemma 1: Let $T$ be a tree rooted at vertex $r$. Let $v_1,v_2,\cdots,v_k$ be the children of $r$ (from left to right). Suppose not all vertices $v_i$ have degree $1$. Then, it is possible to swap the labels on $(r,v_i)$ and $(r,v_j)$ for any $i < j$ while ensuring that every other label stays in its own subtree. Proof: Without loss of generality, assume that $v_1$ has degree $\ge 2$. The following sequence of operations suffice. $\bullet$ Spin $r$ clockwise $i-1$ times. $\bullet$ Spin $v_1$ clockwise once. $\bullet$ Spin $r$ clockwise $j-i$ times. $\bullet$ Spin $v_1$ counterclockwise once. $\bullet$ Spin $r$ counterclockwise $j-i$ times. $\bullet$ Spin $v_1$ clockwise once. $\bullet$ Spin $r$ counterclockwise $i-1$ times. $\square$ To finish this step, we just have to move $l_e$ to the parent edge of $c_i$ by repeatedly spinning the label up the tree, and similarly move $l_f$ to the parent edge of $c_j$. Then, apply Lemma 1 to swap the labels of the parent edges of $c_i$ and $c_j$. This shows that we can decrease $m$ and eventually move each label in the correct subtree, as desired. Step 2: Make all subtrees $S_i$ have a labeling of even parity. Firstly, we prove a helpful lemma. Lemma 2: Let $T$ be a tree rooted at vertex $r$. Let $v_1,v_2,\cdots,v_k$ be the children of $r$ (from left to right) and the corresponding edge labels be $l_1,l_2,\cdots,l_k$. Suppose $v_1$ has degree at least $2$ and its leftmost child is $w_1$ with edge label $w$. Then, it is possible to swap the edge labels $l_1$ and $w$ while cyclically shifting $l_2,\cdots,l_k$ to the left while leaving other labels intact (i.e. now the edges from $r$ have labels $w,l_3,l_4,\cdots,l_k,l_2$). Proof: The following sequence of operations suffice. $\bullet$ Spin $v_1$ clockwise once. $\bullet$ Spin $r$ clockwise once. $\bullet$ Spin $v_1$ counterclockwise once. $\bullet$ Spin $r$ counterclockwise once. $\bullet$ Spin $v_1$ clockwise once. $\bullet$ Spin $r$ clockwise once. $\bullet$ Spin $v_1$ counterclockwise once. $\square$ Corollary. If the root $r$ has even degree (say $k$), then we can always make the parity of the labeling of each subtree $S_i$ even. Proof. Without loss of generality, suppose $i=1$. If $S_1$ has $\le 1$ edges, its labeling is clearly even. Now, suppose the labeling in $S_1$ is currently odd. Apply Lemma 2 $k-1$ times. Since $k-1$ is odd, the edge labels $l_1$ and $w$ in the lemma are swapped. However, all the other labels are left intact (because cyclically shifting $k-1$ times changes nothing). This swaps a pair of labels in $S_1$ which makes its new labeling even without affecting any other labels. $\square$ Hence, we may assume $r$ has odd degree. Let $C_1,C_2,\cdots,C_m$ be the subtrees among $S_i$ that currently have an odd labeling. If $m$ is odd, then at least one non-root vertex of the tree has even degree (or else this implies every vertex has odd degree and the labeling of the entire tree is odd). Performing a spin on that vertex will make $m$ even. Hence, we assume that $m$ is even. To finish this step, we claim that we can make the labelings of $C_1$ and $C_2$ even without affecting labels outside these subtrees. Clearly, $C_1,C_2$ has $\ge 2$ edges (or else it already has even labeling). Without loss of generality, assume that $C_1 = S_1$ and $C_2 = S_i$ for some $i>1$. Let us apply the following series of operations: $\bullet$ Apply Lemma $2$. $\bullet$ Spin $r$ counterclockwise once. $\bullet$ Apply Lemma $2$, with $S_i$ now treated as the leftmost subtree (i.e. we swap the edge labels of two of $v_i$'s adjacent edges). Notice that after these operations, the parity of $C_1$ and $C_2$ are flipped. Additionally, the labels of $(r,c_2), (r,c_3), \cdots, (r,c_{i-1}), (r,c_{i+1}), \cdots, (r,c_{k})$ are cyclically shifted. However, since $k-2$ is odd, we can repeat this operation $k-2$ times and ensure that the parity of $C_1$ and $C_2$ is even while keeping all labels in the correct subtrees. This completes the proof of this step. Step 3: If $S_i$ is a trivial network, ensure all its labels are correct. Note that $S_i$ has an even labeling after Step $2$. If $S_i$ has $\le 1$ edges, we are done, so assume $S_i$ has $\ge 2$ edges. We may assume without loss of generality $i=1$. Let $v$ be the child of $r$ in $S_1$. Let the labels on the edges adjacent to $v$ be $e_1,e_2,\cdots,e_m$ (in clockwise order). The key observation is that we can swap $e_{i}$ and $e_{i+1}$ by applying Lemma $2$ (after spinning $v$ to make $e_i$ the parent edge), at the cost of cyclically shifting the labels on the other $k-1$ children of $r$ once. Firstly, use this operation to swap all the labels $e_i$ into their correct positions. Suppose we used this operations $t_1$ times. Note that $t_1$ is even, since $S_i$ has an even labeling. Now, we apply Lemma $2$ $2t_2$ times where $t_2$ is some positive integer satisfying $k-1 \mid t_1+2t_2$. Observe that $t_2$ is guaranteed to exist because $t_1$ is even. After these operations, all the edge labels around $r$ are in the correct subtrees, and the subtree $S_1$ is solved completely. This completes the last step. After performing all three steps, we can now safely apply the induction hypothesis on all the nontrivial $S_i$'s and obtain the target labeling, as desired. This proves the inductive step and completes the proof. $\blacksquare$