Finding preferences for G-S algorithm (Algorithm Design Chapter 1 exercise 7) I'm working on Algorithm Design (Kleinberg-Tardos) Chapter 1 exercise 7:

Some of your friends are working for CluNet, a builder of large
communication networks, and they are looking at algorithms for
switching in a particular type of input/output crossbar. Here is the
setup. There are n input wires and n output wires, each directed from
a source to a terminus. Each input wire meets each output wire in
exactly one distinct point, at a special piece of hardware called a
junction box. Points on the wire are naturally ordered in the
direction from source to terminus; for two distinct points x and y on
the same wire, we say that x is upstream from y if x is closer to the
source than y, and otherwise we say x is downstream from y. The order
in which one input wire meets the output wires is not necessarily the
same as the order in which another input wire meets the output wires.
(And similarly for the orders in which output wires meet input wires.)
Figure 1.8 gives an example of such a collection of input and output
wires. Now, here’s the switching component of this situation. Each
input wire is carrying a distinct data stream, and this data stream
must be switched onto one of the output wires. If the stream of Input
i is switched onto Output j, at junction box B, then this stream
passes through all junction boxes upstream from B on Input i, then
through B, then through all junction boxes downstream from B on Output
j. It does not matter which input data stream gets switched onto which
output wire, but each input data stream must be switched onto a
different output wire. Furthermore—and this is the tricky
constraint—no two data streams can pass through the same junction box
following the switching operation. Finally, here’s the problem. Show
that for any specified pattern in which the input wires and output
wires meet each other (each pair meeting exactly once), a valid
switching of the data streams can always be found—one in which each
input data stream is switched onto a different output, and no two of
the resulting streams pass through the same junction box.
Additionally, give an algorithm to find such a valid switching.


This is the algorithm I've came up with so far:

Input wires prefer output wires in the order the signal meets each output wire from source to terminus.
Output wires prefer the source input wires of downstream junctions to source input wires of upstream junctions.
Let M be the matchings after applying the G-S algorithm using the input wires, output wires, and associated preferences
Return the set M of input-to-output wire matchings

I'm having trouble proofing or disproving this algorithm correctly solves the problem. My goal is to show that if 2 data streams meet at the same junction then it leads to an instability in  the matchings. I started by assuming the data streams meet on some arbitrary output wire and a downstream junction exists, but I haven't made any progress past that in showing an instability. The 2 source input wires will prefer this arbitrary output wire over their terminus wire, but there is always a place on this arbirary wire to place a junction such that the arbirary output wire prefers it over the other two junctions - then no instability can exist.
Your algorithm is clean and correct.
Here is an easy proof.
Let $\text{junction}(x,y)$ stand for the junction between input $x$ and output wire $y$. Let $\text{stream}(x,y)$ stand for the stream from input wire $x$ to output wire $y$, which must be switched at $\text{junction}(x,y)$.
The book has proved the Gale-Shapley algorithm must produce a stable and perfect matching. As an application, your algorithm must produce a stable and perfect matching between the input wires and output wires.
Suppose, for the sake of contradiction, an execution of your algorithm produces a matching $M$ that includes $\text{stream}(i,o)$ and $\text{stream}(i',o')$ that meet at some junction $J$. Since $\text{stream}(i,o)$ passes $J$, $J$ is either on the same input wire or the same output wire as $\text{stream}(i,o)$. Similarly, $J$ is either on the same input wire or the same output wire as $\text{stream}(i',o')$. Since input wires are disjoint to each other, $J$ cannot be on $i$ and $i'$ both. Similar, $J$ cannot be on $o$ and $o'$ both. So, $J$ must be either $\text{junction}(i,o')$ or $\text{junction}(i',o).$

Suppose $J$ is $\text{junction}(i,o')$.

Since $\text{stream}(i,o)$ passes $J$, $J$ is upstream to $\text{junction}(i,o)$ on input wire $i$, i.e, $i$ prefers $o'$ to $o$.
Since $\text{stream}(i',o')$ passes $J$, $J$ is downstream to $\text{junction}(i',o')$ on output wire $o'$, i.e, $o'$ prefers $i$ to $i'$.

So $(i, o')$ is an instability with respect to $M$.

Otherwise, $J$ must be $\text{junction}(i',o)$. Symmetrically, we will get that $(i', o)$ is an instability with respect to $M$.


However, $M$ is a stable matching. We have arrived at a contradiction. $\quad\checkmark$