Reference no: EM132846774

The cycle graph on n nodes, denoted Cn, is a graph in which all n nodes are connected in a closed chain. Examples of C3 and C4 are shown in Figure 1. In the lecture on network exchange, we learn about the concepts of stability and instability. In this problem, you'll prove a general principle about network exchange between players organized into a cycle graph. For each part of this question, a short explanation (perhaps with an attendant graph or two for illustration if you need it) should suffice.

(a) Prove that under the one-exchange rule, any amount of money x placed uniformly upon each of the edges ofC3will result in instability.

(b) Prove that under the one-exchange rule, any amount of money x placed uniformly upon each of the edges ofC4will result in stability.

(c) Now, we'll attempt to generalize the results of (a) and (b) to a cycle on any number of nodes: in particular, can you show a general principle about the stability or instability of a cycle on an even or odd number of nodes (respectively), under uniform edge values and the one-exchange rule? This doesn't have to be a formal proof, but you should at least give a rigorous explanation (or a counterexample, if you believe such a principle does not exist).