  For an Enriques surface $S$, the non-degeneracy invariant $\mathrm{nd}(S)$
retains information on the elliptic fibrations of $S$ and its polarizations. In
the current paper, we introduce a combinatorial version of the non-degeneracy
invariant which depends on $S$ together with a configuration of smooth rational
curves, and gives a lower bound for $\mathrm{nd}(S)$. We provide a SageMath
code that computes this combinatorial invariant and we apply it in several
examples. First we identify a new family of nodal Enriques surfaces satisfying
$\mathrm{nd}(S)=10$ which are not general and with infinite automorphism group.
We obtain lower bounds on $\mathrm{nd}(S)$ for the Enriques surfaces with eight
disjoint smooth rational curves studied by Mendes Lopes-Pardini. Finally, we
recover Dolgachev and Kond\=o's computation of the non-degeneracy invariant of
the Enriques surfaces with finite automorphism group and provide additional
information on the geometry of their elliptic fibrations.
