The reduced expressions for a given element w of a Coxeter group (W,S) can be regarded as the vertices of a directed graph R(w); its arcs correspond to the braid moves. Specifically, an arc goes from a reduced expression \overrightarrow{a} to a reduced expression \overrightarrow{b} when \overrightarrow{b} is obtained from \overrightarrow{a} by replacing a contiguous subword of the form stst... (for some distinct s,t∈ S) by tsts... (where both subwords have length m_s,t, the order of st∈ W). We prove a strong bipartiteness-type result for this graph R(w) : Not only does every cycle of R(w) have even length; actually, the arcs of R(w) can be colored (with colors corresponding to the type of braid moves used), and to every color c corresponds an opposite color c^op (corresponding to the reverses of the braid moves with color c), and for any color c, the number of arcs in any given cycle of R(w) having color in {c,c^op} is even. This is a generalization and strengthening of a 2014 result by Bergeron, Ceballos and Labbé.