Why do Benes networks form bipartite graphs when you build a constraint graph for them?
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.