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.



Assigning positive edge weights to a graph so that the weight incident to each vertex is 1.
Here is a solution along the lines of JBL's answer.


First a couple of definitions:



> 
> A [disjoint cycle cover](http://en.wikipedia.org/wiki/Vertex_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](http://en.wikipedia.org/wiki/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.


