A lower bound for nodal count on discrete and metric graphs

According to a well-know theorem by Sturm, a vibrating string is divided into exactly n nodal intervals by zeros of its n-th eigenfunction.
The Courant nodal line theorem carries over one half of Sturm's theorem for the strings to the theory of membranes: Courant proved
that n-th eigenfunction cannot have more than n domains. A discrete analogue of Sturm's result (for discretizations of the interval)
was discussed by Gantmacher and M.Krein.

Recently, it was discovered by Schapotschnikow that the nodal count for the Schrodinger operator on trees (where each edge is
identified with an interval of the real line and some matching conditions are enforced on the vertices) is exact too: zeros of the n-th eigenfunction
divide the tree into exactly n subtrees. We discuss two extensions of this result. One deals with the same continuous Schrodinger operator
but on general graphs and another deals with discrete Schrodinger operator on combinatorial graphs.

The result that we derive applies to both types of graphs: the number of nodal domains of the n-th eigenfunction is bounded below
by n-l, where l is the number of links that distinguish the graph from a tree (defined as the dimension of the cycle space or the rank
of the fundamental group of the graph).