# Non-factorizable graphs in which every edge can be extended to a maximum matching

All graphs in this question are finite, simple, undirected, and unweighted. A graph is said to be factorizable if has a perfect matching, and non-factorizable otherwise. An edge in a graph is said to be allowed if it belongs to some maximum matching of the graph. Call a graph $G$ permissive1 if every edge of $G$ is allowed.

I am interested in the properties of non-factorizable permissive graphs. What do we know about these? Where can I read up more on such graphs?

I could find quite a bit of existing work, both structural [1, 2] and algorithmic [3], on factorizable permissive graphs, which are called matching-covered graphs in the literature. However, I could not find anything at all about the case when every edge of a graph belongs to some maximum matching of the graph, and the graph itself does not have a perfect matching. What properties do such graphs have? Do we know something about their structure?

1 My terminology, not standard.

• What do you call a maximum matching? I have seen this terminology to describe matchings of a graph that cannot be extended with another edge. In this case, any matching is a subset of a maximal matching in a finite graph, and in particular every edge belongs to a maximal matching. – zarathustra Apr 14 '15 at 7:21
• @zarathustra: "matchings of a graph that cannot be extended with another edge" are called maximal matchings, as you yourself do in your second sentence. A maximum matching (in a graph without weights, as are those in my question) is a matching of the largest size. I am interested in edges which belong to maximmum matchings and not just those which belong to maximal matchings; these latter are, as you pointed out, not very interesting. – G Philip Apr 14 '15 at 8:25
• My bad, I really should have thought about this for some more seconds before posting this silly comment. – zarathustra Apr 14 '15 at 8:43

The the Edmonds-Gallai decomposition could be what you're looking for. It decomposes a graph into sets $A$, $B$ and $C$, where $A$ is all the vertices missed by at least one maximum matching, $B = N(A)$, and $C$ is all other vertices. Basically, every maximum matching matches vertices in $B$ to odd components of $G - B$ in $A$. In $G - B$, $C$ consists of even components with perfect matchings.

If you follow what this means for a permissive graph, $B$ must be an independent set, since such edges must not be used in a maximum matching. Furthermore, there are no edges from $C$ to the rest of the graph (so if we assume $G$ is connected, $C$ is empty). That's quite a bit of structure right there. I believe the components of $A$ are automatically permissive, and that any of the edges from $A$ to $B$ can automatically be used in maximum matchings, but I'm not sure.

Edit: I noticed the Lovasz article you cite basically makes the same points I was making above, so you may have been aware of this information. But regardless quite a bit is known about such graphs.

• The components of $A$ are factor-critical (remove any vertex from a component, and the rest of the component has a perfect matching), which implies both that we may use any matching of $B$ into $A$ in a maximum matching of $G$, and that the components of $A$ are permissive. – Gregory J. Puleo Apr 14 '15 at 17:24
• Thank you. Sadly, my question arose in fact from observing that graphs for which (i) part $C$ of the Gallai-Edmonds decomposition is empty and (ii) part $B$ is independent, are permissive; my question was prompted by my inability to find any more properties of such graphs. I guess I should have stated this in my question. – G Philip Apr 14 '15 at 18:16
• Also: that any edge from $A$ to $B$ can be used in a maximum matching follows directly from the definition of a permissive graph. And as @GregoryJ.Puleo observed, since deleting any one vertex from a component $H$ of $A$ results in a subgraph $H'$ with a perfect matching, deleting an additional vertex from $H'$ gives us a subgraph $H''$ whose matching size is exactly one less than that of $H$. In particular this implies that the component $A$ is also permissive. – G Philip Apr 14 '15 at 18:17

I think your problem can be reduced to just looking at matching-covered graphs. Let $G$ be a graph and let $\mu$ be its matching number. Let $S$ be the set of all vertices covered by all maximum matchings. Let $G'$ be the larger graph obtained by adding a new independent set of size $|V(G)| - 2\mu$, adjacent to the vertices of $V(G)-S$.

If $G'$ is well-covered, then $G$ is permissive: given any $e \in E(G)$, we can extend to a perfect matching in $G'$, whose restriction to $G$ must be a matching of size $\mu$. On the other hand, if $G$ is permissive then $G'$ is well-covered: given any $e \in E(G')$, either $e \in E(G)$ in which case we can use permissiveness to extend to a maximum $G$-matching and then fix the leftover vertices with the independent set, or else $e$ joins some $v \in V(G) - S$ to the independent set, in which case we can take some maximum $G$-matching that misses $v$ and fix the leftovers (necessarily including $v$) with the independent set, using the edge $e$.

Using this trick, you can probably "transfer" results about matching-covered graphs to your context.

• Thank you. To rephrase what you said using the terminology of the question: Let $G,\mu,S$ be as in your answer. We construct $G'$ by adding an independent set of vertices, call it $T$, of size $|V(G)|-2\mu$ to $G$ and then adding all possible edges between $T$ and $V(G)\setminus{S}$. Now $G'$ has a perfect matching: take any maximum matching of $G$, and match the leftover vertices with vertices in $T$. The fact you prove is that $G'$ is permissive if and only if $G$ is permissive. This construction is probably the reason why nobody cares about permissive graphs without perfect matchings.! – G Philip Apr 15 '15 at 16:25