# Graphs constructed from sums of perfect matchings

Consider the following natural procedure for constructing graphs from perfect matchings in graphs with even number of vertices.

Let $$V$$ be the set of vertices of cardinality $$|V|=2n$$ and let $$\mathcal{M}=\lbrace{M_1,M_2,\ldots, M_k\rbrace}$$ be a collection of perfect matchings of vertices in $$V$$ (understoood as graphs whose edges form a partition of $$V$$ into two element disjoint subsets). Let $$E(\mathcal{M})=\bigcup_{i=1}^k E(M_i)$$ be the union of all the edges appearing in perfect matchings in $$\mathcal{M}$$. We now define a graph whose edge set is precisely $$E(\mathcal{M})$$, i.e. $$G(\mathcal{M})=(V,E(\mathcal{M}))$$.

Question: Does this construction have a name in the literature? If so, were the graphs constructed in this way studied from the perspective of extremal graph theory? I have in mind results in which the size of the collection $$\mathcal{M}$$ plays an analogous role to the number of edges in classical results in that field, like the Erdős–Stone or Kővári–Sós–Turán theorems.

Remark: Although it is possible to lower bound the number of edges in a graph based on the number of prefect matchings (see for example discussion in the question Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs), I suspect that stronger results concerning forbidden subgraphs could be derived for the class of graphs constructed in this way. Specifically, classical results on forbidden subgraphs assumed that subgraphs whose existence we want to exclude have fixed size, while the number of vertices of the ambient graph increases. I hope that this limitation can be lifted for the class of graphs considered here.

• One trivial thing is that these graphs are $k$-edge-colourable. Commented Mar 7, 2022 at 0:52
• Another trivial thing is that these are 1-factorable multigraphs (that is multigraphs which can be decomposed into perfect matchings), hence regular multigraphs. A google search for 1-factorable multigraphs will turn up some papers using this language. Note that not every regular multigraph is 1-factorable though. Commented Mar 9, 2022 at 20:00
• @LouisD The OP just wrote union, not multiset union, so I don't think multigraphs were intended. I could be wrong. Commented Mar 14, 2022 at 12:18
• @BrendanMcKay True. But I meant it in the sense that if the OP views it as a multigraph, it may help lead to some relevant literature. Basically, given a multigraph you can decide to only view the underlying graph, but not the other way around; so there may be some benefit to temporarily thinking of it as a multigraph. Commented Mar 14, 2022 at 17:33

Deciding if a given graph (or type of graph) can be constructed this way would seem the more likely question. When it can, there is sometimes a name for a particular construction of this type. The circle method is one of several to construct a round robin tournament for $$k+1$$ players when $$k$$ is odd: A $$k$$ day tournament where each player plays one match each day and at the end all pairs have played. Consider the players as vertices of a complete graph $$K_{k+1}$$ and color the edges according to the day that pair plays their match. This decomposes the $$\binom{k+1}2$$ edges into $$k$$ perfect matchings.

Digression: There is much work on deciding if a graph $$G$$ is $$k$$-vertex colorable.
Maximum degree $$\lt k$$ is certainly a sufficient condition.
Here is a construction of such a graph: Start with $$k$$ disjoint vertex sets (some perhaps empty) and add some edges, but only between vertices in different sets. The result is certainly $$k$$-vertex-colorable and every such graph arises that way. But the construction does not have a name as far as I know.

Here are some more interesting properties for a regular graph. Consider a simple graph $$G$$ which is regular of degree $$k.$$ Then the vertex coloring number is at most $$k+1$$ and could be $$2.$$ The edge coloring number is at least $$k.$$ We might wonder if it has one or the other of these properties:

I) It can be vertex colored with $$k+1$$ colors so that each vertex has one neighbor of each color other than it's own.

II) It can be $$k$$-edge colored.

The complete graph $$K_{k+1}$$ somewhat trivially has property I.

It is less obvious that, for $$k$$ odd, $$K_{k+1}$$ has property II. One way of proving this is the circle method mentioned above.

Another interesting result is that, for $$k$$ odd, property I implies property II: Given the coloring of $$G$$, color the vertices of $$K_{k+1}$$ with the same colors and consider a $$k$$-edge coloring of that complete graph as just mentioned. Now color each edge of (the vertex colored) $$G$$ with the same color as the correspondingly colored edge of the complete graph.

To get back to your question, it is immediate that property I precisely says that $$G$$ can be constructed in this way:

• Consider $$k+1$$ disjoint vertex classes, each of the same size. Then choose $$\binom{k+1}2$$ matchings, one between each pair of classes.

While property II ($$G$$ is $$k$$-regular and $$k$$-edge colorable) precisely says that it arises from your construction:

• Take $$k$$ edge disjoint perfect matchings ($$1$$-factors) on some $$2m$$ points. (I'm assuming simple graphs and $$k>0$$.)

But I don't know that either construction has a name in general.

The construction can easily be used to create a $$k$$-regular bipartite graph. But it turns out the converse is true as well. A $$k$$-regular bipartite graph has a perfect matching and hence $$k$$ disjoint perfect matchings. So every regular bipartite graph has property II.

• Related to my comment above. One way to decide if a graph can be constructed in this way is to first check whether the graph can be embedded into a k-regular multigraph. If not, then it cannot. If so, then are any of the k-regular multigraphs it can be embedded into 1-factorable? Commented Mar 14, 2022 at 17:39

A graph constructed with a collection of perfect matchings is called a matching covered graph.

• The question is about the (putative) name of a very particular construction of matching covered graphs. Commented Mar 23, 2022 at 12:35
• @AlexM. I don't see that it is particularly special other than that we know an upper bound on the number of perfect matchings need to cover every edge. Commented Mar 23, 2022 at 13:08