# Do all induced subgraphs of powers of cycles have a perfect matching

Do all independence induced subgraphs of powers of cycles have a distinct 1-factor? By independence induced, I mean those induced subgraphs which are formed by removing a maximal independent set of vertices. If not, which indpendence induced subgraphs of powers of cycles have a distinct 1-factor?

I believe that all odd powers of even order cycles have all their independence induced subgraphs each having a 1-factor. This is because, perfect matchings can be taken by pairing two maximal independent sets of vertices(considering independent edges between them). However, I doubt it for the case of even powers of cycles. Consider the power of cycle $$C_8^2$$, the second power of cycle on $$8$$ vertices . Here, we label the vertices from $$0$$ to $$7$$ and the maximal independent sets of vertices are $$[0,4], [1,5], [2,6], [3,7]$$, where the two independent vertices are put in one independent set of square brackets. The edges, of which there are $$16$$ are $$(01), (60),(70), (02);(71), (12), (13), (23), (24), (34), (35), (45), (46), (56), (57), (67)$$, where the two numbers in brockets dente the edge joining the left numbered vertex to right numbered vertex. If we consider the induced subgraph formed by deleting the vertices $$[3,7]$$, we see that the induced subgraph seems not to have a distinct(all independent edges distinct from previous 1-factors of independent induced subgraphs) 1-factor. Any light on this observation? Thanks beforehand.

• The graph should be regular and have a even numbers of vertices. – Bullet51 May 3 at 8:53
• @Bullet51 Yes, powers of cycles are regular(cayley), and of even degree . So do you mean to say that all even powers of cycles have 1-factorizable independence induced subgraphs? My $C_8^2$ example shows that this may not be the case – vidyarthi May 3 at 8:55
• These are meant to be necessary conditions for 1-factors to exist. See the Wikipedia article for that. – Bullet51 May 3 at 8:57
• @Bullet51 thanks for that. Slightly modified the question – vidyarthi May 3 at 9:02