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.



Number of distinct perfect matchings/near perfect matchings in an induced subgraph
Instead of adding yet more comments, here’s an answer that might shoot down a lot of conjectures you might have hoped.


Consider the 4-regular circulant graph on 16 vertices where we connect vertices $x,y$ iff $x-y \in \{\pm 1, \pm 4\}$ (subtraction and vertex labels all viewed mod 16).


Then delete the vertices $\{0, 3,5, 8\}$, which is the neighborhood of the vertex $4$. After deleting this, we’re left with 12 vertices, which form two connected components (vertex 4 is isolated, and the other 11 vertices form a connected subgraph). This induced subgraph has no near-perfect matchings since it has two connected components of odd cardinality.


So whatever it is you might be hoping for, it’s probably false (except perhaps for powers of a cycle, for which there’s so much structure that there might not be much room for anything interesting to happen [haven’t thought too much about that case]). Let me know how this example fits in with whatever you were hoping for.


