Return to Answer

Let $G$ be finite. Then a weighting of the desired form exists if and only if every edge of the graph is contained in a perfect matching.

First, suppose every edge is contained in a perfect matching. Simply take the convex combinations of the matchings (considered as weightings with weight 1 on the edges of the matching and weight 0 on the other edges) and win.

Now, suppose your graph has a weighting of the desired form. The given conditions imply that this weighting belongs to the matching polytope of the graph. Since the matching polytope contains a point with coordinate sum at least $\frac{|V|}{2}$ (namely, your point), it must contain a vertex with coordinate sum at least $\frac{|V|}{2}$. But the vertices are matchings, and each matching contains at most $\frac{|V|}{2}$ edges, so in fact there must be a vertex with exactly this coordinate sum, i.e., a perfect matching. In particular, your weighting lies on the face of the polytope whose vertices are precisely the perfect matchings of the graph, and so it is a convex combination of perfect matchings. Since it is positive in every coordinate, there must be a vertex that is positive in every coordinate, i.e., every edge must be contained in some perfect matching.

An earlier version of this answer solved the problem in the case that "positive" is replaced by "nonnegative". In that case, the condition becomes "the graph contains a perfect matching".

Edit: this is completely broken, sorry! I leave it up for the record.

Let $G$ be finite. Then a weighting of the desired form exists if and only if every edge of the graph is contained in a perfect matching.

First, suppose every edge is contained in a perfect matching. Simply take the convex combinations of the matchings (considered as weightings with weight 1 on the edges of the matching and weight 0 on the other edges) and win.

Now, suppose your graph has a weighting of the desired form. The given conditions imply that this weighting belongs to the matching polytope of the graph. Since the matching polytope contains a point with coordinate sum at least $\frac{|V|}{2}$ (namely, your point), it must contain a vertex with coordinate sum at least $\frac{|V|}{2}$. But the vertices are matchings, and each matching contains at most $\frac{|V|}{2}$ edges, so in fact there must be a vertex with exactly this coordinate sum, i.e., a perfect matching. In particular, your weighting lies on the face of the polytope whose vertices are precisely the perfect matchings of the graph, and so it is a convex combination of perfect matchings. Since it is positive in every coordinate, there must be a vertex that is positive in every coordinate, i.e., every edge must be contained in some perfect matching.

An earlier version of this answer solved the problem in the case that "positive" is replaced by "nonnegative". In that case, the condition becomes "the graph contains a perfect matching".

It's possible if and only if the graph contains a perfect matching:

If there is a perfect matching, then obviously we can put weight 1 on the edges of the matching and weight 0 on the other edges and win.

Conversely, suppose there's a point meeting your condition. Your conditions imply that this point belongs to the matching polytope of the graph. Since the matching polytope contains a point with coordinate sum at least $\frac{|V|}{2}$ (namely, your point), it must contain a vertex with coordinate sum at least $\frac{|V|}{2}$. But the vertices are matchings, and each matching contains at most $\frac{|V|}{2}$ edges, so in fact there must be a vertex with exactly this coordinate sum, i.e., a perfect matching.

Edit: Gjergji Zaimi points out that this doesn't give strictly positive weights. But it's easy to adjust the argument: restrict to the face of the matching polytope whose vertices are the perfect matchings. We can get $c_e > 0$ if and only if there is a vertex in which $c_e > 0$, i.e., if and only if the edge $e$ is contained in a perfect matching. So, we have a weighting with strictly positive weights if and only if every edge of the graph is contained in a perfect matching.

Let $G$ be finite. Then a weighting of the desired form exists if and only if every edge of the graph is contained in a perfect matching.

First, suppose every edge is contained in a perfect matching. Simply take the convex combinations of the matchings (considered as weightings with weight 1 on the edges of the matching and weight 0 on the other edges) and win.

Now, suppose your graph has a weighting of the desired form. The given conditions imply that this weighting belongs to the matching polytope of the graph. Since the matching polytope contains a point with coordinate sum at least $\frac{|V|}{2}$ (namely, your point), it must contain a vertex with coordinate sum at least $\frac{|V|}{2}$. But the vertices are matchings, and each matching contains at most $\frac{|V|}{2}$ edges, so in fact there must be a vertex with exactly this coordinate sum, i.e., a perfect matching. In particular, your weighting lies on the face of the polytope whose vertices are precisely the perfect matchings of the graph, and so it is a convex combination of perfect matchings. Since it is positive in every coordinate, there must be a vertex that is positive in every coordinate, i.e., every edge must be contained in some perfect matching.

An earlier version of this answer solved the problem in the case that "positive" is replaced by "nonnegative". In that case, the condition becomes "the graph contains a perfect matching".

It's possible if and only if the graph contains a perfect matching:

If there is a perfect matching, then obviously we can put weight 1 on the edges of the matching and weight 0 on the other edges and win.

Conversely, suppose there's a point meeting your condition. Your conditions imply that this point belongs to the matching polytope of the graph. Since the matching polytope contains a point with coordinate sum at least $\frac{|V|}{2}$ (namely, your point), it must contain a vertex with coordinate sum at least $\frac{|V|}{2}$. But the vertices are matchings, and each matching contains at most $\frac{|V|}{2}$ edges, so in fact there must be a vertex with exactly this coordinate sum, i.e., a perfect matching.

It's possible if and only if the graph contains a perfect matching:

If there is a perfect matching, then obviously we can put weight 1 on the edges of the matching and weight 0 on the other edges and win.

Conversely, suppose there's a point meeting your condition. Your conditions imply that this point belongs to the matching polytope of the graph. Since the matching polytope contains a point with coordinate sum at least $\frac{|V|}{2}$ (namely, your point), it must contain a vertex with coordinate sum at least $\frac{|V|}{2}$. But the vertices are matchings, and each matching contains at most $\frac{|V|}{2}$ edges, so in fact there must be a vertex with exactly this coordinate sum, i.e., a perfect matching.

Edit: Gjergji Zaimi points out that this doesn't give strictly positive weights. But it's easy to adjust the argument: restrict to the face of the matching polytope whose vertices are the perfect matchings. We can get $c_e > 0$ if and only if there is a vertex in which $c_e > 0$, i.e., if and only if the edge $e$ is contained in a perfect matching. So, we have a weighting with strictly positive weights if and only if every edge of the graph is contained in a perfect matching.