Suppose we define a summation graph $G$ as follows:

Each vertex $v \in G$ has a unique but unknown value ascribed to it. Each edge $e \in G$ is labelled with the sum of the values of the two vertices it joins.

This construction corresponds to a system of equations where each equation is of the form $v_a + v_b = e_{ab}$ where $v_1$ and $v_2$ correspond to the unknown values of two vertices $a$ and $b$, and $e_{ab}$ the value of the edge joining the two.

Now, if there is any odd cycle, it's known that there will always be a unique solution for just that cycle. But with an even cycle, there are either an infinite number of possible values, or an inherent contradiction in the values of the edges that make a solution impossible.

So my question is this: is it possible that there is some bipartite graph (which has no odd cycles, but can have a bunch of even cycles joined together) that has a configuration of values with a unique solution?


No, you can just add $x$ to the nodes in one part and $-x$ to the nodes in the other part to get another solution.

It might be possible to get such a case if your values had to be non-negative.

  • $\begingroup$ I had a feeling this was the case. Thanks. $\endgroup$
    – Joe Z.
    Jul 4 '13 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.