  For a permutation $\pi$ in the symmetric group $S_n$ let the {\it total
degree} be its valency in the Hasse diagram of the strong Bruhat order on
$S_n$, and let the {\it down degree} be the number of permutations which are
covered by $\pi$ in the strong Bruhat order. The maxima of the total degree and
the down degree and their values at a random permutation are computed. Proofs
involve variants of a classical theorem of Tur\'an from extremal graph theory.
