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.

  • 3
    $\begingroup$ The generalization is false: Consider any balanced complete bipartite graph. $\endgroup$ Jun 21, 2019 at 16:14
  • $\begingroup$ @Bullet51 thanks, but what if the condition $\Delta\ge3$ and non-bipartite is added to vertex transitivity. And, what about the first proposition on powers of cycles? $\endgroup$
    – vidyarthi
    Jun 21, 2019 at 16:25

1 Answer 1


Yes, it is possible to find a perfect/near perfect matching in the case of powers of cycles when one non-singleton set of maximal independent vertices of the given form is removed. This is because, the cycle $$\{i-1;i+1;i+2\ldots;i+k;i+k+2;\ldots\ldots i-2(=(i-1)+(n-1)\bmod n);i-1\}$$ is Hamiltonian in the induced subgraph. Thus, by taking an alternating path in the cycle, we obtain the desired perfect/near perfect matching.

The case of any vertex transitive graphs is clearly false, however it may remain open for the subcase of vertex transitive, non-bipartite with maximum degree $\ge3$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.