A lower bound for nodal count on discrete and metric graphs

We study the number of nodal domains (maximal connected regions on which a function has constant sign) of the eigenfunctions of Schrodinger operators on graphs. Under a certain genericity condition, we show that 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. Our results apply to operators on both discrete (combinatorial) and metric (quantum) graphs. They complement already known analogues of a result by Courant who proved the upper bound n for the number of nodal domains. To illustrate that the genericity condition is essential we show that if it is dropped, the nodal count can fall arbitrarily far below the number of the corresponding eigenfunction. In the Appendix we review the proof of the case l = 0 on metric trees which has been obtained by other authors.