  Every simple finite graph $G$ has an associated Lov\'asz-Saks-Schrijver ring
$R_G(d)$ that is related to the $d$-dimensional orthogonal representations of
$G$. The study of $R_G(d)$ lies at the intersection between algebraic geometry,
commutative algebra and combinatorics. We find a link between algebraic
properties such as normality, factoriality and strong $F$-regularity of
$R_G(d)$ and combinatorial invariants of the graph $G$. In particular we prove
that if $d \geq \text{pmd}(G)+k(G)$ then $R_G(d)$ is $F$-regular in finite
characteristic and rational singularity in characteristic $0$ and furthermore
if $d \geq \text{pmd}(G)+k(G)+1$ then $R_G(d)$ is UFD. Here $\text{pmd}(G)$ is
the positive matching decomposition number of $G$ and $k(G)$ is its degeneracy
number.
