What is the relation between matchings and edge coverings?

These are the Gallai identities. The proof of the relationship between matchings and edge covers can also be found on MSE, though that's not quite what you were asking:

• Prove that the sum of minimum edge cover and maximum matching is the vertex count

However, the proof does not give a clean one-to-one correspondence between matchings and edge covers. That's impossible, because there is usually not the same amount of each. Some examples:

• let $G$ be the star graph $K_{1,n-1}$ (with a central vertex attached to $n-1$ vertices of degree $1$). Then it has $n$ matchings, $n-1$ of which are maximum (the empty set, and $n-1$ matchings of size $1$), but only one edge cover (we need to take all $n-1$ edges).
• In the complete bipartite graph $K_{2,n-2}$, the situation reverses. There are only $1 + 2(n-2) + (n-2)(n-3)$ matchings (the terms count matchings of size $0, 1, 2$ respectively). However, there are $2^{n-2}-2$ minimum edge covers (by taking one edge from each vertex on the side with $n-2$ vertices, making sure that they don't all go to the same destination) and many more larger edge covers.

What we can do is the following:

Maximal Matching $\to$ Edge Cover. Suppose $M$ is a maximal matching: we cannot simply add any edge to $M$ to make a bigger matching. Then we can easily (but not uniquely) find an edge cover $C$ such that $|M|+|C|=n$. To find $C$, start by including all edges of $M$, then go through each vertex not covered by $M$, and add an arbitrary edge that does cover it. Usually, there are many ways to add these edges.

Why does this have size $n-|M|$? Well, we covered $2|M|$ vertices with the $|M|$ edges of $M$, and then needed $n-2|M|$ edges to cover the remaining $n-2|M|$ vertices, for a total of $n-|M|$ edges.

Why did $M$ need to be maximal? If $M$ is not maximal, we might end up covering two vertices outside $M$ with the same edge, so then the edge cover $C$ we get has $|C| < n-|M|$. Aside from that, everything would still work.

Minimal Edge Cover $\to$ Matching. Suppose $C$ is a minimal edge cover: we cannot simply remove any edges of $C$ to get a smaller edge cover. Then we can easily (but not uniquely) find a matching $M$ such that $|M|+|C|=n$.

It can be shown that $C$ has the structure of a star forest: as a subgraph, it has some number of components, each isomorphic to a star graph. (In particular, this allows for components that have a single edge.) To find a matching $M$ of size $n-|C|$, simply select one edge from each component.

Why does this have size $n-|C|$? Well, $C$ is a forest, and any forest with $n$ vertices and $c$ edges has $n-c$ components.

Why did $C$ need to be minimal? Well, this argument doesn't work, but worse than that: if $C$ is a non-minimal edge cover, it's usually possible for $|C|$ to be much bigger than $n$, in which case it does not even make sense to find a matching of size $n-|C|$.

Perfect Matching $\leftrightarrow$ "Perfect Edge Cover". In the special case where the graph has a perfect matching, that perfect matching is also a minimum edge cover. (Nobody actually calls it a "perfect edge cover".) In such a graph, maximum matchings and minimum edge covers are one and the same, and have $n/2$ edges.

Matching $\leftrightarrow$ Edge Cover in Cycle Graphs. As far as I can tell, this is just pure coincidence unrelated to the broader identity, but if $G$ is the cycle graph $C_n$, or the disjoint union of cycles, then the complement of every matching is an edge cover, and vice versa. A matching must include at most one of the two edges out of every vertex, so its complement must include at least one of the two edges out of every vertex, which is exactly the definition of an edge cover.

Edit: When I wrote this answer I misread the question as asking for an explicit bijection between the two sets that were known to have the same size, namely: the vertices on one side and the disjoint union of a maximal matching and a minimal edge cover on the other.

By pure good fortune, this does answer the OP's modified question: finding a natural correspondence between maximal matchings and minimal edge covers. This correspondence is surjective in both directions, but not necessarily injective in either (so may not be a function in either direction).

Specifically this answer shows that every maximal matching is a subset of a minimal edge cover, and every minimal edge cover contains a maximal matching.

Thus containment gives us a natural relation between maximal matchings and minimal edge covers.

In the case where there exists a complete matching, this relationship becomes the identity (hence is a function and is a bijection).

Here is a way to pair off vertices with the disjoint union of edges in a maximal matching and edges in a minimal edge cover.

Say a star is a graph consisting of an initial vertex, and some positive number of edges each incident to the initial vertex.

Let a graph $G$ have no isolated vertices. Say a star decomposition of $G$ is a subgraph of $G$ containing all the vertices, where each connected component is a star.

Say a star decomposition of $G$ is maximal if it has the most connected components.

Theorem

• i) Every maximal matching sits inside a maximal star decomposition.

• ii) Taking one edge from each connected component of a maximal star decomposition gives a maximal matching.

• iii) Every maximal star decomposition is a minimal edge cover.

• iv) Every minimal edge cover is a star decomposition.

The pairing off is now clear: Take a maximal star decomposition. Its edges form a minimal edge cover $C$ by (iii). Let $M$ consist of one edge from each star. By (ii) $M$ is a maximal matching. Pair off each initial vertex with the edge in $M$ incident to it. Pair off the remaining vertices with the edge in $C$ incident to them.

Proof of (i) and (ii): Let $M$ be a maximal matching. Vertices not incident to $M$ cannot be adjacent to each other, or we could obtain a larger matching. Also if $(v_1,v_2)\in M$ and $s\neq t$ are vertices not incident to $M$, with $s$ adjacent to $v_1$ and $t$ adjacent to $v_2$, then replacing $(v_1,v_2)$ with $(v_1,s)$ and $(t,v_2)$, yields a larger matching. Thus we may extend $M$ to a star decomposition, by connecting the vertices not incident to $M$, to just one end of the edges in $M$.

Conversely, given a star decomposition, just pick one edge from each star to get a matching. Thus the star decomposition obtained from a maximal matching must be maximal, or we could obtain a larger matching from a larger star decomposition.

Similarly the matching obtained from a maximal star decomposition must be maximal, or we could obtain a larger star decomposition from a larger matching.

Proof of (iii) and (iv): A minimal edge covering cannot contain any loops, nor can it contain three edges in a line (or you could remove the middle one and still have an edge cover. Thus it must be a star decomposition.

Conversely, a star decomposition is an edge covering by definition. The number of edges in a star decomposition of $G$ is the number of vertices of $G$, minus the number of connected components of the star decomposition.

Thus a minimal edge covering must be a maximal star decomposition, or the larger star decomposition would yield a smaller edge covering.

Similarly, a maximal star decomposition must be a minimal edge covering, as a smaller edge covering would be a larger star decomposition.