The answer is $ n+1$. If we have $ n$ segments, we have only one cycle in the graph and so we can only reach at most $ n$ different permutations, but we need $ n!$. So suppose we have $ n+1$. Construct the segments so that $ V_i V_{i+1}$ are connected (including $ V_n V_1$) and $ V_1 V_4$ are connected. That is, we have an $ n$-cycle and a $ 4$-cycle. In other words, we can basically pick any $ 4$ consecutive pieces and permute them in a $ 4$-cycle by shifting all pieces with the $ n$-cycle so those $ 4$ are on the $ 4$-cycle and then shifting back. Suppose we have $ 5$ adjacent pieces $ a,b,c,d,e$. Then we can get $ c,d,a,b,e$ $ c,a,b,e,d$ $ a,b,e,c,d$. Namely, $ c,d,e$ became $ e,c,d$. So we can generate any $ 3$-cycle, too. Using the $ 3$ or $ 4$ cycles, simply move $ C_1$ to $ V_1$, then move $ C_2$ to $ V_2$ without changing $ C_1$'s place. We can guarantee we will be able to move $ C_1, C_2, \ldots C_{n-2}$ into the right positions in this way using the $ 3$-cycle. The only issue is if we end up with $ C_{n-3}, C_{n-2}, C_n, C_{n-1}$ in $ V_{n-3}, V_{n-2}, V_{n-1}, V_n$ respectively. This is easy to fix: use the $ 4$-cycle to get $ C_{n-1}, C_{n-3}, C_{n-2}, C_n$, and then the $ 3$-cycle to get $ C_{n-3}, C_{n-2}, C_{n-1}, C_n$, and that finishes it.