# Number of distinct perfect matchings/near perfect matchings in an induced subgraph

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.

• Do you mean max degree $Delta$ ... or regular degree $Delta$ ... or ??? – EGME May 15 at 8:48
• @EGME actually I mean $\it{max}$ $\it{degree}$ $\Delta$, but regular is somewhat easier to answer, I think – vidyarthi May 15 at 8:50
• Question. If we take the complete bipartite graph on 3+3=6 vertices ($K_{3,3}$) and we remove all the vertices on one side, the remaining graph has no edges (and hence no perfect matchings). How does this fit in with your question? – Pat Devlin May 15 at 16:06
• Perhaps a silly question, but can’t we (easily?) find induced subgraphs with no perfect matchings? For instance, subgraphs with an odd number of vertices. And if you mean “maximal matchings” instead of perfect, we could probably find a subgraph where the degrees are too small. – Pat Devlin May 15 at 18:06
• Still might be confused. Take the 3-regular graph on 16 vertices found here mathoverflow.net/questions/98385/…. You can remove an independent set of size 5 so as to split the graph up into a bunch of components of odd size, so it won’t have anything close to a perfect matching. In fact, for higher degree, you could probably make that example worse by having one cut vertex in the middle connected to a bunch of stuff. – Pat Devlin May 15 at 18:20

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.