The (weak) Bruhat graph 
of order 
is the simple graph having have all permutations
of 
as vertices, and with an edge
between pairs of permutations that differ by an adjacent
transposition. The 
-Bruhat graph is the Cayley graph
of the symmetric group 
generated by adjacent transpositions
(Hurlburt 2011). The Bruhat graphs of orders 1 to 4 are illustrated above.
Bruhat graphs are antipodal.
The permutations and edges corresponding to 
are illustrated above.
Special cases are summarized in the following table.
