Let $X$ be an irreducible smooth projective curve over an algebraically closed field $k$ of characteristic $p$, with $p > 5$. Let $G$ be a connected reductive algebraic group over $k$. Let $H$ be a Levi factor of some parabolic subgroup of $G$ and $\chi$ a character of $H$. Given a reduction $E_H$ of the structure group of a $G$-bundle $E_G$ to $H$, let $E_\chi$ be the line bundle over $X$ associated to $E_H$ for the character $\chi$. If $G$ does not contain any ${\rm SL}(n)/Z$ as a simple factor, where $Z$ is a subgroup of the center of ${\rm SL}(n)$, we prove that a $G$-bundle $E_G$ over $X$ admits a connection if and only if for every such triple $(H ,\chi ,E_H)$, the degree of the line bundle $E_\chi$ is a multiple of $p$. If $G$ has a factor of the form ${\rm SL}(n)/Z$, then this result is valid if $n$ is not a multiple of $p$. If $G$ is a classical group but not of the form ${\rm SL}(n)/Z$, then this criterion for the existence of connection remains valid even if $p \geq 3$.