Consider a Class 1 graph with degree $\Delta\ge3$ and the induced subgraph formed by deleting a set of independent vertices of cardinality $\left\lfloor\frac{n}{\Delta}\right\rfloor$. Then, what is the number of disjoint near perfect matchings(when the induced subgraph is odd) or perfect matchings(when the induced subgraph is even) which cover the edges of the graph maximally?

The same question for Class 2 graphs, is, what is the number of disjoint near-perfect matchings or perfect matchings of the induced subgraph formed by deleting an independent set of vertices that cover the edges of the graph maximally?

Subquestion: What if the graph were to be a power of cycles, or, a circulant graph?

I feel that on removal of an independent set of vertices(of cardinality $\left\lfloor\frac{n}{\Delta}\right\rfloor$), the number of disjoint near perfect matchings in a Class 1(or atleast powers of cycles) is atleast $\Delta-2$. Is this true?, or, are there any counterexamples? Is the matching polynomial of any use here? I think the matching generating polynomial gives the number of distinct perfect matchings but they do not take into consideration whether the edges of graph are covered or not. For example, the complete graph on six vertices is said to have $15$ distinct perfect matchings. But, only $5$ distinct perfect matchings are sufficient to cover the graph maximally(covers all edges). So, the maximal matchings I discuss here are disjoint and sort of nearly factorise the induced subgraph. I also think perfect matchings( or near-perfect matchings) of induced subgraphs of regular graphs can be thought of as permanents of the adjacency matrix of the induced subgraph. Can this approach be used? Thanks beforehand.

7more comments