An old problem in mathematical physics deals with the structure of the dispersion relation of the Schrödinger operator $-Δ+V(x)$ in $R^n$ with periodic potential near the edges of the spectrum. A well known conjecture says that generically (with respect to perturbations of the periodic potential) the extrema are attained by a single branch of the dispersion relation, are isolated, and have non-degenerate Hessian (i.e., dispersion relations are graphs of Morse functions). The important notion of effective masses in solid state physics, as well as Liouville property, Green's function asymptotics, etc. hinge upon this property. The progress in proving this conjecture has been slow. It is natural to try to look at discrete problems, where the dispersion relation is (in appropriate coordinates) an algebraic, rather than analytic, variety. Such models are often used for computation in solid state physics (the tight binding model). Alas, counterexamples exist in some discrete situations. We start establishing the following dichotomy: the non-degeneracy of extrema either fails or holds in the complement of a proper algebraic subset of the parameters. The known counterexample has only two free parameters. This might be too tight for genericity to hold. We consider the maximal $Z^2$-periodic two-atomic nearest-cell interaction graph, with nine edges per unit cell and the discrete "Laplace-Beltrami" operator on it. We then use methods from computational and combinatorial algebraic geometry to prove the genericity conjecture for this graph. We show three different approaches to the genericity, which might be suitable in various situations. It is also proven in this case that adding more parameters does not destroy the genericity result. We list all "bad" periodic subgraphs of the one we consider and discover that in all these cases genericity fails for "trivial" reasons only.