Why do Benes networks form bipartite graphs when you build a constraint graph for them?

Question

I was learning about Benes networks and was wondering why they formed bipartite graphs (and thus are two colorable) when one draws a constraint graph for them. The constraint graph is based on the intuition that we don't want two paths for packets to intersect because we want to show that the congestion is 1 (i.e. that even in the worst case, packet paths don't collide). This is what at least I think is implied from the following OCW notes:

If one looks at page 3 of the notes it says:

Color (i.e., label) the vertices of your graph red and blue so that adjacent vertices get different colors. Why must this be possible, regardless of the permutation π?

I understand it maybe for this small example, but why would the above be true in general?

I guess I didn't really understand why every constraint graph had to be bipartite or why it had to be 2 colorable.

For example, how do I know that as I form the constraint graph, that I will not have a some clique of size 3 or more? If this were the case it would be bad, because I would for sure need 3 colors at least!

I did notice that when we form the constraints, we form them by first considering a matching of the output packets that might collide and another set of constraint about packets that might collide when arriving to the destination. This two constraints adds two matching to the graph. Maybe the union of matchings forms bipartite graphs?

Answer 1

You didn't explain what Beneš networks are (note that your course notes use the wrong accent on the s!), but from the notes it seems that they describe FFT algorithms. In particular, they seem to be layered graphs. Such graphs have $L$ layers $1,\ldots,L$, and edges only go between adjacent layers $i,i+1$. Color all nodes in odd layers with one color and all nodes in even layers with another color. Since $i,i+1$ have different parities, this is a valid coloring.