Assigning positive edge weights to a graph so that the weight incident to each vertex is 1.

Question

Let $\Gamma=(G,E)$ be a connected undirected graph, with no loops or multiple edges. $G$ is finite or countably infinite. For each edge $e=\{x,y\}\in E$, we assign a positive, symmetric edge weight $c_e := c_{\{x,y\}} = c_{xy} = c_{yx}$. I would like to know for which graphs $\Gamma$ it is possible to choose $(c_e)_{e\in E}$ so that for each $x\in G$,

\begin{equation*} \sum_{y\sim x} c_{xy} = 1. \end{equation*}

For example, this is possible on any $d-$regular graph if one sets $c_e \equiv 1/d$. The graph with vertex set $\{x,y,z\}$ and edges $\{x,y\}$ and $\{y,z\}$ shows that it is not always possible.

Answer 1

Here is a solution along the lines of JBL's answer.

First a couple of definitions:

A disjoint cycle cover of a graph is a collection of cycles of our graph which are disjoint subgraphs, and contain all the vertices of our graph. A special case of a disjoint cycle cover is a perfect matching, for instance.

We will call the the permanent of a graph, the permanent of its adjacency matrix

An easy fact is that the permanent of a graph counts its disjoint cycle covers. Now, to our result:

Theorem: A graph admits edge weights as in the problem if and only if every edge is contained in a disjoint cycle cover. Equivalently if and only if removing an edge decreases the permanent.

proof:

Suppose the graph $G$ has such weights. Then the matrix $A$ with $a_{ij}$ being the weight of the edge connecting vertices $v_i$ and $v_j$, is doubly stochastic, and thus by the Birkhoff-von Neumann theorem can be written as a convex combination of permutation matrices. For every edge of $G$, there is a non zero term $a_{ij}$ in $A$ which means that there is a permutation matrix in our sum with a $1$, in the $ij$ entry, call this matrix $M_{ij}$. The first observation is that $M_{ij}$ has all zeros on the diagonal, and secondly that all it's non-zero entries correspond to edges in $G$. This collection of edges is of course a disjoint cycle cover.

Now for the other direction, each cycle cover can be assigned weights as in the problem (just assign $1/2$ to all edges in proper cycles and $1$ to all isolated edges). So taking an appropriate convex combination of all such covers gives us weights for $G$.

A special case is of course when all edges are contained in perfect matchings, but this property doesn't characterize all graphs as in the question, as the example I gave in the comment to JBL's answer shows (also just look at odd cycles). Which is why one must include more general cycle covers.

---

Perhaps it is a bit more clear if we phrase it in the following way. When restricting to bipartite graphs, the property of each edge being contained in a disjoint cycle cover is equivalent to every edge being in a perfect matching (there are no odd cycles). Now the result above follows because weights on our graph induce weights on its bipartite double cover which sum to 1 at each vertex. A disjoint cycle cover of a graph is equivalent to a perfect matching of its bipartite double cover.

Answer 2

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".