Consider a power of cycle graph $C_n^k\,\,,\frac{n}{2}>k\ge2$, represented as a Cayley graph with generating set $\{1,2,\ldots, k,n-k,\ldots,n-1\}$ on the Group $\mathbb{Z}_n$. Supposing I remove an independent set of vertices of the form $\{i,i+k+1,\ldots,\left\lfloor\frac{n}{k+1}\right\rfloor+i\}$ or a single vertex. Then, is it possible to obtain a perfect/ near perfect matching when I remove the non single independent set of vertices always? If not, then is it possible in case the graph is an even power of cycle?
I hope yes in the case of even power of cycle, as we can pair the vertices between any two independent sets of the above form or between the indpendent set and the single vertex to get a maximal matching which is near perfect(in case the order of induced subgraph is odd) or perfect(in case the order of the induced subgraph is even). It could also be seen by observing that when the maximal independent set of vertices(as given above) is removed, we have a Hamiltonian cycle in the induced subgraph(proof of which is not clear to me, but we may use Bondy-Chvátal or construct an explicit Hamiltonian cycle using the remaining elements). Any counterexamples? Also, can we generalize this, if true, to any vertex transitive graph, that is, does there exist an indpendent set(non-singleton) of vertices, such that removing that set induces a perfect/near-perfect matching? Thanks beforehand.
