## Abstract

Sturm's oscillation theorem states that the *n*th eigenfunction of a Sturm–Liouville operator on the interval has *n*−1 zeros (nodes) (Sturm 1836 *J. Math. Pures Appl.* **1**, 106–186; 373–444). This result was generalized for all metric tree graphs (Pokornyĭ *et al.* 1996 *Mat. Zametki* **60**, 468–470 (doi:10.1007/BF02320380); Schapotschnikow 2006 *Waves Random Complex Media* **16**, 167–178 (doi:10.1080/1745530600702535)) and an analogous theorem was proved for discrete tree graphs (Berkolaiko 2007 *Commun. Math. Phys.* **278**, 803–819 (doi:10.1007/S00220-007-0391-3); Dhar & Ramaswamy 1985 *Phys. Rev. Lett.* **54**, 1346–1349 (doi:10.1103/PhysRevLett.54.1346); Fiedler 1975 *Czechoslovak Math. J.* **25**, 607–618). We prove the converse theorems for both discrete and metric graphs. Namely if for all *n*, the *n*th eigenfunction of the graph has *n*−1 zeros, then the graph is a tree. Our proofs use a recently obtained connection between the graph's nodal count and the magnetic stability of its eigenvalues (Berkolaiko 2013 *Anal. PDE* **6**, 1213–1233 (doi:10.2140/apde.2013.6.1213); Berkolaiko & Weyand 2014 *Phil. Trans. R. Soc. A* **372**, 20120522 (doi:10.1098/rsta.2012.0522); Colin de Verdière 2013 *Anal. PDE* **6**, 1235–1242 (doi:10.2140/apde.2013.6.1235)). In the course of the proof, we show that it is not possible for all (or even almost all, in the metric case) the eigenvalues to exhibit a diamagnetic behaviour. In addition, we develop a notion of ‘discretized’ versions of a metric graph and prove that their nodal counts are related to those of the metric graph.

## 1. Introduction

Nodal domains were first presented in full glory by Chladni's sound figures. By the end of the eighteenth century, Chladni was performing the following demonstration: he spread sand on a brass plate and stroked it with a violin bow. This caused the sand to accumulate in intricate patterns of nodal lines—the lines where the vibration amplitude vanishes. The areas bounded by the nodal lines are the nodal domains. The first rigorous result on nodal domains is probably Sturm's oscillation theorem, according to which a vibrating string is divided into exactly *n* nodal intervals by the zeros of its *n*th vibrational mode [1,2] (see also [3], p. 454). In the next century, Courant treated vibrating membranes and proved that the number of nodal domains of the *n*th eigenfunction of the Laplacian is bounded from above by *n* [4] (see also [3], p. 452). Pleijel further restricted the possible nodal domain counts and showed, for example, that the Courant bound can be attained only a finite number of times [5]. These are some of the earlier results in the field of counting nodal domains. This field gained an exciting turn when Blum *et al.* [6] showed that the nodal count statistics may reveal the nature of the underlying manifold—whether its classical dynamics are integrable or chaotic. This opened a new research direction of treating the nodal count from the inverse problems perspective. One aspect of this research is rephrasing the famous question of Kac by asking ‘Can one *count* the shape of a drum?’ (see [7] for Kac's original question). Namely what can one learn about an object (manifold, graph, etc.), knowing the nodal counts of all of its eigenfunctions? One way to treat this question is by studying the direct (rather than inverse) problem and developing formulae which describe nodal count sequences [8–13]. Such formulae are expected to reveal various geometric properties of the underlying object which one seeks to reveal. One can also study inverse nodal problems by comparing the nodal information with the spectral one. A well-established conjecture in the field claims that isospectral objects have different nodal count sequences. After its first appearance in a paper by Gnutzmann *et al.* [14], the conjecture initiated a series of works on nodal counts of various objects, either affirming the conjecture in certain settings [15–19], or pointing out counterexamples [20,21]. The general validity of this conjecture is still not well understood. The most recent approach in the study of nodal counts describes the nodal domain count (and even morphology) of individual eigenfunctions in terms of partitions. This was triggered by Helffer *et al.* [22] who studied Schrödinger operators on two-dimensional domains using partitions of the domain. They provided characterization of the morphology and number of nodal domains of eigenfunctions which attain the Courant bound. Following this, Band *et al.* [23] used a partition approach for metric graphs and described the number of nodal points and their location for all eigenfunctions via a Morse index of an energy function. This result initiated similar connections between nodal counts and Morse indices, for discrete graphs and manifolds, which were studied by Berkolaiko *et al.* [24,25]. Finally, three new works show that the response of an eigenvalue to magnetic fields on the graph dictates the nodal count via a Morse index connection. The first of these results was obtained by Berkolaiko [26] for discrete graphs and shortly afterward an additional proof was supplied by Colin de Verdière [27]. Berkolaiko & Weyand [28] provide the last work, for the time being, in this series and it appears in this Theo Murphy Meeting Issue.

This paper adopts the magnetic approach mentioned above to solve inverse nodal problems on both metric and discrete graphs. For metric graphs, ‘nodal lines’ are actually nodal points, and the zeros of the eigenfunction and the nodal domains are the subgraphs bounded in between. For discrete graphs, ‘nodal lines’ are edges connecting two vertices at which the eigenvector differs in sign, and the nodal domains are the subgraphs obtained upon removal of those edges. The main result of this paper is a solution to an inverse nodal problem—under some genericity assumptions, if for all *n* the *n*th eigenfunction has *n*−1 zeros, then the graph cannot have cycles and must be a tree. This result is valid for both metric and discrete graphs, although the assumptions and proof methods of the relevant theorems are different (see §1*d* for exact details). We conclude this introductory part by referring the reader to a collection of articles [29], where a broad view is given on the nodal domain research, its history, applications and the numerous types of objects it concerns.

The paper is organized in the following way. In the rest of the introductory section, we familiarize the reader with all ingredients which play a role in the formulation of the theorems: magnetic operators on both discrete and metric graphs, the connection between both types of graphs and their nodal counts. The last introductory subsection (§1*d*) presents the two main theorems of the paper. Section 2 introduces the three main tools required for the proofs. The next two sections present the proofs of our inverse nodal theorems for both discrete and metric graphs, each in a separate section. Section 5 presents a method of discretizing metric graphs which gives another insight for the proof in §4 and might lead to generalizations of the inverse result. Finally, we discuss the essence of the work and offer directions for further exploration. It is important to emphasize that some of the paper's sections can be read independently of those preceding them. The schematic diagram in figure 1 shows the section dependencies as blocks resting on top of other blocks on which they depend.

### (a) Discrete graphs

Let be a graph with the sets of vertices and edges . All graphs discussed in this paper are connected and have a finite number of vertices and edges. Each edge , *e*={*u*,*v*} connects a pair of vertices, . We exclude edges that connect a vertex to itself and do not allow two vertices to be connected by more than one edge. For some purposes, we would need to consider the directions of the edges. We therefore also define the set of all graph edges, each appears twice with both its possible directions, and hence . We use the notation *e*=(*u*,*v*) to refer to a directed edge which starts at *u* and terminates at *v* and denote the edge with the reversed direction by . For a vertex , its *degree* equals the number of edges connected to it, i.e. . *Functions* on the graph refer to and we now present the operators acting on such functions.

The *normalized Laplacian* is
1.1

The normalized Laplacian is a special case of the *generalized discrete Laplacian* also known as the *discrete Schrödinger operator*, a real symmetric matrix which obeys
1.2and with no constraints on its diagonal values (which are sometimes called in the literature on-site potentials).

These matrices have real eigenvalues which we denote by , ordered increasingly, and the corresponding eigenvectors are denoted by . The spectrum of the normalized Laplacian belongs to the interval [0,2]. We refer the interested reader to many results concerning the spectra of graph matrices and their eigenvectors which can be found in [30–32] and references therein.

The discrete Schrödinger operator can be supplied with a *magnetic potential*, , which is defined as such that . Assigning such a potential to the operator amounts to the following changes:
where **L**_{u,v} are the entries of the previous (zero magnetic potential) Laplacian. Note that this magnetic operator is still Hermitian, and hence has real eigenvalues.

Given a cycle, *γ*=(*v*_{1},…,*v*_{n}), on the graph, we define the *magnetic flux* through this cycle as
The graph's cycles play an important role when introducing magnetic potential. We denote the number of ‘independent’ cycles on the graph as
(assuming the graph is connected). This is also known as the first Betti number, which is the dimension of the graph's first homology. In the following, we often fix some arbitrary *β* independent cycles on the graph, {*γ*_{1},…,*γ*_{β}}, and denote the magnetic fluxes through them by {*α*_{1},…,*α*_{β}}. One can show that given two magnetic potentials, and with the same values for the magnetic fluxes , their corresponding magnetic Laplacians and are unitarily equivalent. This unitary equivalence is also known as the gauge invariance principle and means that the spectrum of the Laplacian is uniquely determined by the values (but not so for its eigenfunctions). We take advantage of this principle, notation-wise, and write the Laplacian and its eigenvalues as functions of the magnetic parameters (fluxes), **L**(** α**) and

*λ*

_{n}(

**), where**

*α***:=(**

*α**α*

_{1},…,

*α*

_{β}). Note that in the special case of a tree graph, the gauge invariance principle means that all magnetic Laplacians are unitarily equivalent to the zero magnetic Laplacian,

**L**(

**0**), and the eigenvalues do not depend on the magnetic potential. More details on magnetic operators on discrete graphs can be found in [33–36].

### (b) Metric (quantum) graphs

A *metric graph* is a discrete graph each of whose edges, , is identified with a one-dimensional interval, [0,*l*_{e}], with a positive finite length *l*_{e}. We use the notation ** l** for the vector whose entries are . We denote a metric graph by . We can then assign to each edge a coordinate,

*x*

_{e}, which measures the distance along the edge from the starting vertex of

*e*. In particular, we have the following relation between coordinates of reversed edges: . We denote a coordinate by

*x*, when its precise nature is unimportant. A function on the graph is described by its restrictions to the edges, , where and we require , for all . Therefore, in effect, there is only a single function assigned to each pair of edges, .

We equip the metric graphs with a self-adjoint differential operator , the *Hamiltonian* or *metric Schrödinger operator*,
1.3where *V* _{e}(*x*) is a real-valued bounded and piecewise continuous function that forms the *electric potential*, and is called the *magnetic potential* and it obeys . It is most common to call this setting of a metric graph with a Schrödinger operator a quantum graph. We will keep calling these graphs metric graphs to distinguish them from their discrete counterpart which we also equip here with an operator of a quantum nature.

To complete the definition of the operator, we need to specify its domain. We denote by *H*^{2}(*Γ*) the following direct sum of Sobolev spaces:
1.4The graph's connectivity is expressed by matching the values of the functions at the common vertices, thus dictating the operator's domain. All matching conditions that lead to the operator (1.3) being self-adjoint have been classified in [37,38,39]. It can be shown that under these conditions the spectrum of is real and bounded from below [39]. In addition, because we consider only compact graphs, the spectrum is discrete and with no accumulation points. We number the eigenvalues in ascending order and denote them (similarly to the discrete case) with and their corresponding eigenfunctions with . We also use *k*_{n}, such that , and say that is the *k*-spectrum of the graph.

As we wish to study the sign changes of the eigenfunctions, we would require their continuity. The only matching conditions which ensure a self-adjoint operator and guarantee that the function is continuous (at the vertices) are the so-called extended *δ*-type conditions at all the graph's vertices.

A function *f*∈*H*^{2}(*Γ*) is said to satisfy the extended *δ*-type conditions at a vertex *v* if

1.

*f*is continuous at , i.e. where is the set of edges starting at*v*(so that*x*_{e}=0 at*v*if ).2. The outgoing derivatives of

*f*at*v*satisfy 1.5where*f*(0) denotes the value of*f*at the vertex (which is uniquely defined owing to the first part of the condition).

In particular, the case *χ*_{v}=0 is often referred to as *Neumann condition* (also called Kirchhoff or standard condition). We call a graph whose vertex conditions are all of Neumann type and whose magnetic and electric potentials vanish everywhere a *Neumann graph* and state our main results for such graphs. A Neumann graph has *λ*_{1}=0 with multiplicity which equals the number of graph components (which is always one throughout this paper) and their *k*-spectrum is therefore real and non-negative. Another useful vertex condition is . This is called a *Dirichlet condition* at the vertex *v*, and can be formally written as (1.5) with . Note that whenever a vertex exhibits a Dirichlet condition, it effectively disconnects all edges connected to this vertex. Similar to the Neumann graph, a *Dirichlet graph* is obtained whenever all vertices are supplied with Dirichlet conditions. The eigenvalues of such a graph are merely a union of spectra of its disjoint edges (with Dirichlet conditions at their endpoints) and are called *Dirichlet eigenvalues*.

An important observation which plays a role in this paper is that the spectrum and eigenfunctions of the graph are not affected if a graph's edge is divided into two parts by introducing a new vertex (of degree two) at an arbitrary point on this edge and supplying it with Neumann conditions. The process (and outcome) of introduction of any number of such vertices on the graph we call the graph's *subdivision* and keep in mind that the spectral properties are invariant with respect to subdivisions. Similar to the definition of discrete graphs, we also exclude edges which connect a vertex to itself and vertices which are connected by more than two edges (reversed to each other). Note, however, that this does not restrict the generality of our results as any metric graph which does have self-cycles or multiple edges can be subdivided to eliminate these defects.

The *magnetic flux* through a cycle, *γ*=(*v*_{1},…,*v*_{n}), is defined as
where the notation *e*∈*γ* means that either *e*=(*v*_{i},*v*_{i+1}) for some *i* or *e*=(*v*_{n},*v*_{1}). The gauge invariance principle introduced in §1a applies to the metric Schrödinger operator as well and allows us to write and *λ*_{n}(** α**), when referring to the operator and its eigenvalues. This obviously holds once some fixed choice

*β*cycles is made, and the notation is adapted to fluxes through these cycles, where

**:=(**

*α**α*

_{1},…,

*α*

_{β}). Two good references for further reading on the general theory of metric (quantum) graphs are [40,41].

### (c) The nodal count

The main focus of this paper is the number of sign changes of eigenfunctions on discrete and metric graphs. When counting sign changes, we always consider eigenfunctions of the zero magnetic potential operators, as otherwise we are not guaranteed to have real-valued eigenfunctions. In addition, in order for the number of sign changes to be well defined, we assume the following.

### Assumption 1.1

*The eigenvalue λ_{n} is simple and the corresponding eigenfunction f_{n} is different from zero on every vertex.*

We call *λ*_{n} a *generic eigenvalue* if it satisfies assumption 1.1 (correspondingly, *f*_{n} is called a *generic* eigenfunction). This assumption is generic with respect to various perturbations to the operator. In the discrete case, such perturbations include changing the non-zero entries of the matrix **L**. For a metric graph, one may perturb either the vertex conditions, the edge lengths or the electric potential. Further discussions can be found in [23,26,42], where this assumption was used.

We now define sign changes (also known as nodal points) and nodal domains and use the same notations for both metric and discrete graphs.

### Definition 1.2

1. Let

*f*_{n}∈*H*^{2}(*Γ*) be generic and the*n*th eigenfunction of the Schrödinger operator on a metric graph. The zeros of*f*_{n}form isolated points on the graph and they correspond to the function's sign changes. Their set is denoted by*Φ*_{n}.2. Let be generic and the

*n*th eigenfunction of the discrete Schrödinger operator on a graph. We say that an edge*e*={*u*,*v*} forms a*sign change (also a nodal point)*of the eigenfunction if*f*_{n}(*u*)*f*_{n}(*v*)<0. The set of these edges is denoted by3. The number of nodal points of

*f*_{n}(for both metric and discrete graphs) is called the*sign change count*or*nodal point count*of*f*_{n}and is denoted by*ϕ*_{n}:=|*Φ*_{n}|.4.

*Γ*∖*Φ*_{n}consists of a few subgraphs disconnected one from the other. These subgraphs are called the*nodal domains*of*f*_{n}and their number, the*nodal domain count*, is denoted by*ν*_{n}.

We also use the general term *nodal count*, when it is either clear or unimportant whether we count nodal points or nodal domains. We remark that if assumption 1.1 is not satisfied owing to zeros on vertices, the definitions above should be modified. There are indeed alternative definitions of the nodal count in such scenarios (see [15]), but their treatment is beyond the scope of this paper.

The known bounds on the nodal count are 1.6and 1.7

In particular, for a tree graph where *β*=0, one obtains ∀*n* *ϕ*_{n}=*n*−1. This result for the interval is the famous Sturm oscillation theorem [1,2] and its generalization for trees was done in [43,44]. The fact that *discrete* tree graphs also have this nodal count is proved in [45–47]. The upper bound of (1.7) (Courant bound) is proved in [48] for discrete graphs and in [49] for metric graphs. For both metric and discrete graphs, the upper bound of (1.7) also proves the upper bound of (1.6) because *ϕ*_{n}≤*ν*_{n}−1+*β*. The lower bound of (1.7) for both metric and discrete graphs is proved in [45] and the same proof works to prove the lower bound in (1.6) (again for both kinds of graphs).

Two recent works which go further than the above bounds (and from which the bounds (1.6), (1.7) can be deduced) characterize the nodal count of an eigenfunction in terms of a Morse index of a predefined energy function [23,25]. These works led to a characterization of the nodal count in terms of Morse indices of magnetic perturbations. This last result is an important tool used in the proofs of this paper and is described in §2*a*.

### (d) The main results of this paper

We start by introducing the notation
Namely *λ*_{n} is a *generic eigenvalue* if and only if .

The two main theorems of this paper are the following.

### Theorem 1.3

*Let* *be a graph supplied with discrete Schrödinger operator, all of whose eigenvalues are generic, i.e.* *. If its nodal point count is such that for all* *, then* *is a tree graph.*

### Theorem 1.4

*Let Γ be a Neumann metric graph with at least one generic eigenvalue greater than zero. Then, Γ has infinitely many generic eigenvalues and exactly one of the following holds:*

1.

*Γ is a tree and for all**and ν*_{n}*=n.*2.

*Γ is not a tree and each of the sets**is infinite.*

These theorems solve the nodal inverse problem for a tree graph. It is interesting to compare the assumptions and the conclusions of the discrete case with the metric one. The metric theorem shows that a generic nodal count cannot be almost like that of a tree—either it equals a tree's nodal count or it differs from it for an infinite subsequence. In addition, it allows one to conclude that the graph is a tree even if non-generic eigenvalues exist (by simply ignoring them) as long as there is at least one positive generic eigenvalue. The discrete theorem seems to assume more than the metric one, as it requires that all the eigenvalues are generic and all of them have the nodal count of a tree (*ϕ*_{n}=*n*−1). Indeed, in the discrete case, ignoring non-generic eigenvalues is not possible—the normalized Laplacian on the triangle graph, for example, has a single generic eigenfunction with the tree nodal count and two others which are non-generic. The metric theorem also allows one to conclude that the graph is a tree based on its *nodal domain* count. There is, however, no analogous result for discrete graphs. As the final comparison point we mention that the metric theorem solves the inverse problem only for the Laplacian (as it is a Neumann graph and there is no potential), whereas the discrete one applies to the more general Schrödinger operator.

## 2. Introducing tools required for the proofs

### (a) The magnetic spectral–nodal connection

This section is devoted to an important connection between the nodal count and the stability of eigenvalues under magnetic perturbation. Such a connection first appeared in [26], where Berkolaiko proved it for discrete graphs. Shortly afterward, the same theorem was reproved by Colin de Verdière who had also shown that the theorem holds for the Hill operator—the metric Schrödinger operator on a single loop graph [27]. The proof of the theorem for a general metric graph, owing to Berkolaiko & Weyand [28], appears in another paper of this Theo Murphy Meeting Issue.

Before stating the relevant theorem, we need to introduce the following notations.

1. The difference of the nodal count from its lower bound (also its value in the tree case) is denoted Hence, we call it the

*nodal surplus*following [26] (it was also called*nodal defect*in [27]).2. The Hessian of the eigenvalue

*λ*with respect to magnetic parameters at the point=*α***0**is denoted by When=*α***0**is a critical point of*λ*(), the Morse index is defined as the number of negative eigenvalues of and it is denoted by .*α*

We collect below the main results of [26–27] into a single theorem which is applicable for both metric and discrete graphs.

### Theorem 2.1 ([26–28])

*Let* *(Γ) be a discrete (metric) graph supplied with a discrete (metric) Schrödinger operator. Let λ*_{n}(** α**)

*and f*

_{n}(

**)**

*α**be an eigenvalue and a corresponding eigenfunction of the magnetic operator such that λ*

_{n}(

**0**)

*and f*

_{n}(

**0**)

*satisfy assumption 1.1. Then, the following holds*.

1.

*The point**α**=***0***is a critical point of the function λ*_{n}(*α**).*2.

*The critical point**α**=***0***is non-degenerate.*3.

*The nodal surplus, σ*_{n}*, of the eigenfunction f*_{n}(**0**)*is equal to the Morse index of this critical point,*

### (b) Ergodic flow on the characteristic torus

It is well known that eigenvalues of a metric graph are given, with their multiplicities, as the zeros of a secular function [50,51],
where
2.1and **A**, **E** and **S** are square matrices of dimension and contain the information about the magnetic fluxes, edge lengths and edge connectivity, respectively. Exact details on the structure of those matrices appear in [41,51] and we just state here the necessary facts which we use later on:

1.

**E**is a diagonal matrix of the form2. For a Neumann graph,

**S**is a constant unitary matrix which does not depend on*k*.3.

**A**is a diagonal matrix which is linear in.*α*4. is a real-valued function.

Let be a metric graph. We write its edge lengths as the following linear combinations:
2.2where all are rational numbers and {*ξ*_{i}}_{i∈I} is a set of *incommensurate* real numbers, i.e. they are linearly independent over the rationals. For example, if all edge lengths are incommensurate, then and the set {*ξ*_{i}}_{i∈I} can be chosen to consist of the edge lengths. On the other extreme, if all ratios of edge lengths are rational, then |*I*|=1 and one can choose *ξ*_{1} to equal any of the edge lengths (or any rational multiple of it). The relations between the edge lengths of the graph, , and the parameters {*ξ*_{i}}_{i∈I} will play an important role later on and we thus define the *length map* as
2.3This map depends on the specific edge lengths of *Γ* (even the dimension of its domain depends on that) and on the specific choice of values for {*ξ*_{i}}_{i∈I}.

We now describe a method introduced by Barra & Gaspard [52], who related the graph eigenvalues to the Poincaré return times of a flow to a surface defined by the zero-level set of the secular function (2.1). We present their method using our length map and start by redefining the secular function 2.4and 2.5

We point out some properties of *F*, which can be deduced from (2.1).

1.

*F*is differentiable.2. because is homogeneous and contains the parameter

*k*only in the product .3.

*F*(;*x*) is periodic in each of the entries of*α*. The period depends on the specific entry,*x**x*_{i}, and is some rational multiple of 2*π*.

The last property allows us to (re)define the function *F*(⋅;** α**) on an |

*I*|-dimensional torus, , with sides depending on the periodicity of

*F*with respect to its parameters, {

*x*

_{i}}

_{i∈I}. Namely and from now on whenever

*F*is mentioned, its

**variable is taken modulus this torus periodicity, even if this is not explicitly written. Property (2) allows us to characterize the graph**

*x**k*-eigenvalues as where is the vector with incommensurate entries chosen above. We therefore may define the following flow on the torus 2.6and the surface 2.7so that the

*k*-spectrum equals the times (i.e. the

*k*values) for which the flow

**(**

*x**k*) pierces

*Σ*

_{α}.

### Remark 2.2

The eigenfunctions which correspond to the graph eigenvalues depend both on the point on the torus and on the specific values of *k* and ** l**. The restriction of the eigenfunction to the graph vertices, however, is a continuous function solely of [50,51]. This last observation is exploited in §§4 and 5.

We end by noting that as the entries of ** ξ** are linearly independent over , the flow (2.6) is ergodic on . This ergodicity is the reason for making the reduction from the set of edge lengths, , to {

*ξ*

_{i}}

_{i∈I}. We could have defined the flow on an -dimensional torus, but then the flow would not necessarily fill the whole torus—it would actually fill a linear subspace given by (modulo the -dimensional torus).

### (c) The spectral connection between metric and discrete graphs

An interesting connection exists between the spectrum of an *equilateral* metric graph, a graph whose edge lengths are all equal, and the spectrum of the discrete graph that shares the same connectivity. This connection is usually stated in terms of the spectrum of the *transition matrix*,
2.8The transition matrix is sometimes referred to as the *difference operator* or even the discrete Laplace operator, but we will not use it here to avoid confusion. One should note that the transition matrix is not symmetric (and thus does not fall under the definition of the generalized Laplacian), but it is closely related to the normalized Laplacian as
2.9where is a diagonal matrix which contains all vertex degrees. If *λ*,*f* are an eigenvalue and an eigenvector of **L**^{(norm)}, then **P** has 1−*λ* and **D**^{1/2}*f* as its corresponding eigenpair. We use this connection between both operators to slightly rephrase a known result which usually refers to the spectrum of the transition matrix.

### Theorem 2.3 ([39,53–56])

*Let* *be a discrete graph and Γ be a metric graph with the same connectivity and such that ∀e l*_{e}*=1. Consider the normalized Laplacian,* *L*^{(norm)}*, on* *and the metric Laplacian with Neumann conditions on Γ. Equip both operators with magnetic fluxes for some choice of β cycles on the graph (the same choice for both* *and Γ). Let μ(**α**)∉{0,2} be an eigenvalue of* *and f(*** α**)

*the corresponding eigenvector. Then*

1.

*All values in the infinite set**are eigenvalues of the magnetic metric Schrödinger operator on Γ. We consider here**as a multi-valued function,*.2.

*When**α**=***0***, the other eigenvalues of the metric Schrödinger operator are the Dirichlet eigenvalues, all of which belong to the set*.3.

*An eigenfunction of the magnetic metric Schrödinger operator corresponding to any of the eigenvalues**equals**D*^{1/2}*f(*)*α**when restricted to Γ's vertices.*

The content of the theorem for the zero magnetic potential case appears in [39,53,55,56], where they mostly treat Neumann vertex conditions (except in [56] where the so-called anti-Kirchhoff conditions are treated as well). A more general derivation that includes electric and magnetic potentials as well as *δ*-type conditions appears in [54]. In most works mentioned above, the results are stated in terms of the transition matrix, (2.8), but we prefer to relate to the normalized Laplacian as theorem 2.1 applies to it.

## 3. Proofs for discrete graphs

Theorem 1.3 brings one of the two results which inspire this paper's title. Its proof appears next and is followed by further results regarding the nodal count of discrete graphs.

### Proof of theorem 1.3.

Assume by contradiction that is not a tree. Namely *β*>0, and we may therefore supply the graph with a magnetic potential and apply theorem 2.1. From the assumption in our theorem, we get for the nodal surplus
We apply theorem 2.1 for *λ*_{n}(** α**)—the third part of the theorem allows us to conclude that

*λ*

_{n}(

**) has a minimum at**

*α***=**

*α***0**, and the second part shows that this minimum is strict. Therefore, the eigenvalue sum, , also has a strict minimum at

**=**

*α***0**. However, because the diagonal entries of the Laplacian do not depend on the magnetic parameters,

**, we get that trace {**

*α***L**(

**)} is a constant function of**

*α***. Hence, we arrive at a contradiction, owing to . □**

*α*The essence of the proof above is to show that the zero sequence is not a valid candidate as a nodal surplus sequence. This is done by identifying *trace* {**L**(** α**)} as a spectral invariant independent of the magnetic potential. We wish to point out similar results which are obtained from such a method. An immediate next step would be to observe that trace {

**L**

^{2}(

**)} is also a constant function of**

*α***. Computing its Hessian and expressing it in terms of the eigenvalues and their Hessians, , gives 3.1where we have used ∀**

*α**n*∀

*i*(∂/∂

*α*

_{i})

*λ*

_{n}(

**0**)=0, which we get from theorem 2.1 (part (1)). Similarly, the magnetic invariance of

*trace*{

**L**(

**)} gives 3.2Combining (3.2) and (3.1) allows us to prove the following.**

*α*

### Proposition 3.1

*Let* *be a graph with* *β* *cycles supplied with discrete Schrödinger operator such that all of its eigenvalues are generic. Its nodal count cannot be of the form*
*for any* *m*.

### Proof.

Assume by contradiction that the graph has the above nodal count. Namely, the graph's surplus sequence is of the form {0,…,0,*β*,…,*β*}. From theorem 2.1, we get that
3.3and
3.4where the first (second) inequality above means that the Hessians are positive (negative) definite quadratic forms. Note that owing to theorem 1.3. We rewrite (3.1) as
where we used (3.3), (3.4) and the fact that eigenvalues are ordered increasingly to get the second line. The last line is proportional to (3.2), which gives the contradiction. □

Carrying on with this route and examining traces of higher powers of the operator shows that in general *trace* {**L**^{k}(** α**)} might depend on the magnetic parameters. More specifically, a direct calculation of

*trace*{

**L**

^{k}(

**)} shows that it can be expressed as an expansion over closed walks of size**

*α**k*on the graph. Examining the dependence of such walks on magnetic parameters brings about the following.

### Theorem 3.2

*Let* *be a non-tree graph (β>0) with discrete Schrödinger operator such that all of its eigenvalues are generic. Then, the size of the graph's shortest cycle (its girth) is
**Alternatively, it also equals* .

### Proof.

The Hessian of trace {**L**^{k}} is obtained in terms of Hessians of the eigenvalues as
3.5where we used theorem 2.1 to conclude that *λ*_{n} has a critical point at ** α**=

**0**, and therefore no first derivatives of

*λ*

_{n}appear above. The diagonal entries of

**L**

^{k}can be expressed using closed walks on the graph. We define a

*closed walk*by

*γ*=(

*v*

_{0},

*v*

_{1},…,

*v*

_{k−1}), where for all 0≤

*i*≤

*k*−1 either

*v*

_{i}=

*v*

_{i+1}or (we denote

*v*

_{k}:=

*v*

_{0}and keep in mind that

*γ*is defined up to cyclic permutations). This is similar to the usual notion of closed walks, but we allow the walk to stop at any vertex for a (discrete) while before continuing to the next one. The set of all closed walks of size

*k*, passing through vertex

*v*, is denoted , and we attribute to each walk a weight obtained as a product of all corresponding Laplacian entries, where the notation

*v*:=

*v*

_{0}is implied. The expression above depends on the magnetic parameters, which we omit for the sake of brevity. The diagonal entries of

**L**

^{k}can be now written as Denote by

*κ*the graph's girth. For

*k*<

*κ*, the closed walks do not circulate any cycle, and therefore their weights,

*L*

_{γ}, are independent of magnetic parameters (as can also be seen by a direct calculation of

*L*

_{γ}). We thus get from (3.5) that and it is left to show that this is actually an equality. For

*k*=

*κ*, let

*γ*=(

*v*,

*v*

_{1},…,

*v*

_{k−1}) be a closed walk on the graph that contains one of the graph's cycles. The walk

*γ*must have all of its vertices different from each other, as

*k*is the length of the shortest cycle on the graph. The contribution to [

**L**

^{k}]

_{v,v}comes only from

*γ*and other walks that circulate one of the graph cycles. We may couple all such walks to and get that their contributions are complex conjugates of each other, . From

**L**(

**) being Hermitian and**

*α***L**(

**0**) having negative off-diagonal entries, we get where . As

*γ*circulates one of the graph cycles,

**≠**

*n***0**, and therefore In particular, all such second derivatives which do not vanish have a definite sign, which equals (−1)

^{k+1}. Therefore, summing over all such couples, gives and therefore also This shows that for

*k*=

*κ*, the trace of the Hessian in (3.5) is different from zero and completes the proof. □

### Remark 3.3

Note that the proof would work similarly if the second derivatives are calculated with respect to the magnetic potential on the single edges (rather then on the flux over a cycle). In such a case, the theorem can be extended to include tree graphs as well. In addition, these derivatives are more accessible for computation, especially if we are given only the Laplacian, and the graph's connectivity is unknown, which is relevant as we are dealing with inverse problems.

Theorem 3.2 goes a step forward from theorem 1.3 as it allows one to obtain some information on the graph's cycles. Yet, the information used in this inverse result is purely spectral—eigenvalues and their perturbations with respect to magnetic potentials. It would be interesting to see whether one may obtain results of similar character from the nodal count of the graph. A possible direction might be to examine the magnetic derivatives of traces of powers of the Laplacian (as in the proof of theorem 3.2) or the magnetic derivatives of the coefficients of the characteristic polynomial. Theorem 2.1 would probably be a main tool in such an exploration. Indeed, in the course of the proof of theorem 3.2, we did not exploit the full strength of theorem 2.1 and used it only to claim that all first magnetic derivatives vanish. Applying the spectral–nodal connection which theorem 2.1 offers to gather information on the graph cycles might be an important step in developing a trace formula for the nodal count. A further discussion on this direction is found in §6.

## 4. Proofs for metric graphs

The main result of this paper for metric graphs (theorem 1.4) follows from the next lemma and theorem.

### Lemma 4.1

*Let Γ be a Neumann metric graph with at least one generic eigenvalue greater than zero. Then, Γ has infinitely many generic eigenvalues.*

### Theorem 4.2

*Let Γ be a Neumann metric graph with β>0 cycles and at least one generic eigenvalue greater than zero. Denote by σ the nodal surplus of such an eigenvalue. Then*

1.

*There are infinitely many generic eigenvalues whose nodal surplus equals σ.*2.

*There are infinitely many generic eigenvalues whose nodal surplus equals β−σ.*

We first apply lemma 4.1 and theorem 4.2 to prove theorem 1.4, and then proceed to prove them as well.

### Proof of theorem 1.4.

Observe that *Γ* has infinitely many generic eigenvalues as a direct conclusion of lemma 4.1. If *Γ* is a tree graph then it was proved in [43,44] (see also appendix A in [45]) that the nodal counts of all generic eigenfunctions are *ϕ*_{n}=*n*−1 and *ν*_{n}=*n*. Otherwise, if *Γ* has *β*>0 cycles, assume by contradiction that there are only finitely many generic eigenfunctions with *ϕ*_{n}≠*n*−1. In particular, this means that there is at least one generic eigenfunction for which *ϕ*_{n}=*n*−1, and thus *σ*_{n}=0. We may therefore conclude from theorem 4.2 that there are infinitely many generic eigenfunctions whose nodal surplus is *β* (*ϕ*_{n}=*n*−1+*β*) and get a contradiction.

In order to prove the statement about the nodal domain count, we use the following connection between nodal point count and nodal domain count for metric graphs, which is proved for example in [23] (see there, eqn (1.11) together with lemma 3.2):
4.1Now, assume by contradiction that there are only finitely many eigenfunctions with *ν*_{n}<*n*. Then, there exists some *n*_{1}>*n*_{0} such that for all , *ν*_{n}=*n* and from (4.1) we get that for all , *ϕ*_{n}=*n*−1+*β*. The surplus of all these eigenfunction is *β*. Applying theorem 4.2 gives that there are also infinitely many generic eigenfunctions with surplus equal to zero, but the conclusion in the previous sentence allows for only finitely many surpluses to differ than *β*, and hence the contradiction. □

We now proceed to the proof of lemma 4.1, and bring two additional lemmata, all of which will be used to prove theorem 4.2. In the following, we refer to as the graph eigenvalues, which is valid and done for the sake of simplicity.

### Proof of lemma 4.1.

Let be a vector of incommensurate entries which express the graph edge lengths by (2.2). Let *k*_{0} be a generic eigenvalue of *Γ*. Note that the graph eigenvalues are given as zeros of *F* together with their multiplicities (a property that *F* inherits from , see (2.1) and (2.5)). We therefore get that (d/*dk*)*F*≠0 at simple eigenvalues. As we assumed *k*_{0} to be a simple eigenvalue, we have (d/*dk*)*F*|_{(k0ξ,0)}=** ξ**⋅

**∇**

*F*|

_{(k0ξ,0)}≠0. We know that

*k*

_{0}

**∈**

*ξ**Σ*

_{0}, as

*k*

_{0}is an eigenvalue and

*Σ*

_{0}is the zero set of

*F*(recall §2

*b*). Choose a neighbourhood

*Ξ*of

*k*

_{0}

**on**

*ξ**Σ*

_{0}such that

**⋅**

*ξ***∇**

*F*|

_{(x,0)}≠0 for all

**∈**

*x**Ξ*. Recall (remark 2.2) that the values the eigenfunction obtains on the graph vertices are a continuous function of

**. From the genericity of**

*x**k*, we know that its corresponding eigenfunction does not vanish on the vertices and we may therefore choose

*Ξ*small enough such that this property holds for all

**∈**

*x**Ξ*. As the flow is ergodic, the set

*Ξ*⊂

*Σ*

_{0}will be pierced an infinite number of times by the flow, yielding infinitely many eigenvalues. Our choice of

*Ξ*guarantees both that these eigenvalues are simple and that their corresponding eigenfunctions do not vanish on vertices. □

### Lemma 4.3

*Let* *be a vector of incommensurate entries which express the graph edge lengths by (2.2). Let* *k*(**0**)≠0 *be a generic eigenvalue. The Hessian of this eigenvalue with respect to the magnetic fluxes at* ** α**=

**0**

*is given as*4.2

*where*

*denotes the Hessian of the secular function*

*F*(

*k*(

**0**)

**;⋅)**

*ξ**with respect to its magnetic parameters and*

**∇**

*F*

*is the gradient of*

*F*(⋅;

**0**)

*taken with respect to its coordinates on the torus*.

### Proof.

The eigenvalue *k*(** α**) is given implicitly as the solution of

*F*(

*k*(

**)**

*α***;**

*ξ***)=0. Take the second total derivatives of this expression with respect to any two magnetic fluxes, Evaluate the above at the point**

*α***=**

*α***0**and use ∀

*i*(∂

*k*/∂

*α*

_{i})|

_{α=0}=0 (theorem 2.1, part (1)) to get that the second and the third terms above vanish and we are left with 4.3We now repeat the argument in the proof of lemma 4.1 to conclude that if

*k*(

**0**) is simple, then (

*d*/

*dk*)

*F*|

_{(k(0)ξ,0)}=

**⋅**

*ξ***∇**

*F*|

_{(k(0)ξ,0)}≠0. Thus, we divide (4.3) by

**⋅**

*ξ***∇**

*F*|

_{(k(0)ξ,0)}to get (4.2). □

### Lemma 4.4

*The secular function F of a Neumann graph exhibits the following symmetry*:
4.4

### Proof.

Let and . Choose some with incommensurate entries. There exists such that ** x**≡

*k*

**modulo . The required symmetry (4.4) is now obtained from the following series of equalities: The first and last equalities result from property (2), mentioned after the definition of**

*ξ**F*on the torus, (2.5). The second equality can be deduced from (2.1) together with the linearity of

**A**(

**) and the observation that**

*α***S**(

*k*) is real and

*k*-independent for a Neumann graph. Finally, the third inequality (from the first to the second line) is due to being real. □

### Proof of theorem 4.2.

Denote the edge lengths of *Γ* by the vector ** l** and choose an incommensurate set which is related to graph edge lengths by (2.2). Let

*k*be a generic eigenvalue of

*Γ*whose nodal surplus is

*σ*. The Hessian of

*k*is given by (4.2) in lemma 4.3 and we know from theorem 2.1 (part (2)) that it is non-degenerate. We may therefore choose a neighbourhood

*Ξ*of

*k*

**on**

*ξ**Σ*

_{0}such that is non-degenerate for all

**∈**

*x**Ξ*, and thus the number of negative eigenvalues of stays constant in this neighbourhood. This number equals the Morse index of the eigenvalue and it equals

*σ*by an application of theorem 2.1 (part (3)). As the flow is ergodic, the set

*Ξ*⊂

*Σ*

_{0}is pierced an infinite number of times by the flow, yielding infinitely many eigenvalues. All of these eigenvalues are generic if

*Ξ*is chosen small enough, as can be shown by repeating the argument in the proof of lemma 4.1. Each of these eigenvalues would have this same Morse index,

*σ*, by (4.2). The nodal surplus of each of these eigenvalues is therefore also equal to

*σ*, according to theorem 2.1 (part (3)) and this proves the first statement in our theorem. The second statement is proved with the aid of the symmetry (4.4) in lemma 4.4, which allows us to conclude from which we get 4.5The LHS has

*σ*negative eigenvalues, and therefore the RHS has

*β*−

*σ*negative eigenvalues. From (4.4), we also deduce

*Ξ*⊂

*Σ*

_{0}⇒−

*Ξ*⊂

*Σ*

_{0}(where −

*Ξ*:={

**; −**

*x***∈**

*x**Ξ*}). Now, use again the ergodicity of the flow to conclude that the set −

*Ξ*is pierced an infinite number of times by the flow and all resulting eigenvalues have Morse index

*β*−

*σ*, which equals their nodal surplus following theorem 2.1. □

### Remark 4.5

The proof above essentially enables the proof of the metric inverse nodal theorem (theorem 1.4). One might note that the proof here is of a different nature from the proof of the discrete inverse nodal theorem (theorem 1.3), where we have identified the trace of the operator as a spectral invariant independent of magnetic potential. One can find, however, a similarity between the proofs, as the antisymmetric relation (4.5) points to the possibility to average the Hessians over whole torus and shows that the magnetic dependence cancels.

### Remark 4.6

In the course of the proof, we have used an equality between the Morse index of a particular eigenvalue and the Morse index of the secular function *F* evaluated at the appropriate point. A similar relation appears in appendix E of [27] where the Morse index of an eigenvalue is expressed in terms of the Morse index of the characteristic polynomial evaluated at this eigenvalue.

### Remark 4.7

The symmetry which lemma 4.4 describes can already be exhibited on the level of the Schrödinger operator on the graph. One can show that the symmetry amounts to conjugation of all the eigenvalues (see (1.3)), which actually leaves the spectrum invariant as it is real. Lemma 4.4 tells us that the transformation changes the sign of the *k*-eigenvalues, which also leaves the spectrum invariant. This spectral symmetry was exploited in [28,27] to prove that the eigenvalues have critical points at ** α**=

**0**.

## 5. Discretized versions of a metric graph

Here, we present a connection between a certain metric graph and various discrete graphs with similar nodal surplus. These discrete graphs can be obtained from the metric one by means of a simple construction and they will be called its discretized versions. This correspondence between a metric graph and its discretized versions is interesting on its own and can also be used as a tool to provide an additional proof for theorem 4.2, and thus also for the inverse result in theorem 1.4. More interestingly, this might be used to further extend theorem 1.4 for graphs with general vertex conditions and electric potentials (see remark 5.4).

The construction starts by picking a vector of incommensurate entries such that the graph edge lengths are given by (as in §2*b*). The specific discretized version we construct is characterized by a selection of
5.1Note that the set is non-empty. In order to show this, one can approximate ** ξ** by some rational vector, , such that has all positive entries (just as does). Note that (see (2.2)), and therefore the vector can now be multiplied by a common divisor of its entries to turn its entries to natural numbers, while retaining it in .

Take the underlying discrete graph of the metric graph, *Γ*, and equip each edge with *j*_{e}−1 new vertices of degree two, which will split this edge into *j*_{e} new edges. This (new) discrete graph is denoted and called *a discretized version of* *Γ*. Note that a discretized version is not uniquely determined by *Γ*. The set of all possible discretized versions is given by . This set depends on the ‘nature of incommensurability’ of the original edge lengths, , i.e. the rational dependencies between these lengths. However, one can verify that does not depend on the particular choice of incommensurate representatives, {*ξ*_{i}}_{i∈I}.

Note that one may convert the discretized graph, , back into a metric graph (different from *Γ*) by setting all of 's edge lengths equal to one. One would then get a metric graph with the same connectivity as *Γ*, but with integer edge lengths given by ** j**. We denote this metric graph by and it will turn out to be useful in the course of proving the following.

### Theorem 5.1

*Let Γ be a Neumann metric graph with β>0 cycles and let* *be a discretized version of Γ. Let μ∉{0,2} be a generic eigenvalue of* *L*^{(norm)} *on* *whose nodal surplus is σ. Then*

1.

*Γ has infinitely many generic eigenvalues whose nodal surplus equals σ.*2.

*Γ has infinitely many generic eigenvalues whose nodal surplus equals β−σ.*

### Remark 5.2

It is important to emphasize that the theorem holds for *all* discretized versions, , of a metric graph, *Γ*.

### Remark 5.3

One should note that the theorem is empty if the spectrum of the chosen discretized version consists only of the eigenvalues {0,2} and other non-generic eigenvalues. The only connected graph which has no eigenvalues different from {0,2} is the single edge graph (e.g. lemma 1.8 in [31]). Nevertheless, it does not fit our theorem as it has no cycles. Yet, there are discrete graphs (with cycles) all of whose eigenvalues that are different from {0,2} are not simple. The *n*-cube graph forms such an example (example 1.6 in [31]). Following the previous remark, one may still wonder whether for given a metric graph there is always *some* discretized version for which theorem 5.1 is not empty. We are not aware of possible answers to this question.

### Proof.

Start by proving the theorem for an equilateral graph *Γ*, and a specific discretization of it. We may assume without loss of generality that for all , *l*_{e}=1 (as nodal count is indifferent to scaling). We choose a discretized version, , which has the same vertex and edge sets and connectivity as *Γ* does (it is obtained by choosing ** j**=(1,…,1) in (5.1)). Let

*μ*(

**0**)∉{0,2} be a generic eigenvalue of

**L**

^{(norm)}(

**0**) on whose eigenvector is

*f*and nodal surplus is

*σ*. Consider the magnetic Laplacian,

**L**

^{(norm)}(

**), apply theorem 2.1 and obtain that**

*α**μ*(

**) has a critical point at**

*α***=**

*α***0**and its Morse index is . Theorem 2.3 shows that are eigenvalues of the magnetic Schrödinger operator on

*Γ*and we wish to obtain their Morse indices at

**=**

*α***0**. First, exclude the values ±1 from the domain of and consider it as a union of single valued ‘branch’ functions . With this notation, those eigenvalues of

*Γ*resulting from

*μ*(

**) are given by where the subscript (**

*α**p*) is not to be confused with the serial number of

*λ*

_{(p)}in

*Γ*'s spectrum. Each of those eigenvalues is obtained as a function of

*μ*(

**), which has a well-defined monotonicity:**

*α*1. For even values of

*p*,*λ*_{(p)}(*μ*()) is a monotonic strictly increasing function of*α**μ*(). The Hessians of*α**λ*_{(p)}() and*α**μ*() at*α*=*α***0**are therefore equal up to a positive multiple, which yields equality of their Morse indices, 5.22. For odd values of

*p*,*λ*_{(p)}(*μ*()) is a monotonic strictly decreasing function of*α**μ*(). Therefore, in this case, the Hessians of*α**λ*_{(p)}() and*α**μ*() at*α*=*α***0**are equal up to a negative multiple, which yields the following relation of their Morse indices: 5.3

We may now apply the metric version of theorem 2.1 for the eigenvalues *λ*_{(p)}, but first verify that they satisfy the theorem's assumptions. Their simplicity (at ** α**=

**0**) follows from theorem 2.3 as

*μ*(

**0**) is simple and

*μ*(

**0**)∉{0,2} (which guarantees that , i.e. different from the Dirichlet eigenvalues). In addition, according to theorem 2.3 (part (3)), the restriction of the eigenfunction of

*λ*

_{(p)}(

**0**) to the graph vertices equals

**D**

^{1/2}

*f*, where

*f*, the eigenvector corresponding to

*μ*(

**0**), is different from zero on all vertices, by the theorem's assumption. The nodal surplus of

*λ*

_{(p)}, which we denote by

*σ*

^{(Γ)}(

*λ*

_{(p)}) can therefore be expressed as 5.4and 5.5which proves the theorem for the case of an equilateral metric graph if its discretization is given by choosing

**=(1,…,1).**

*j*If the graph *Γ* is not equilateral and the discretized version, , is arbitrary, then there is no exact expression that connects both spectra of *Γ* and . The route we take this time is to turn into an equilateral graph, , all of whose edge lengths equal one. Therefore, there are Morse index connections similar to (5.2), (5.3) between and . We then show that infinitely many eigenvalues of *Γ* share the same Morse index (and hence the same surplus) as eigenvalues of and this yields the desired statements in the theorem. This is the content of the rest of the proof.

Let *μ*(**0**)∉{0,2} be a generic eigenvalue of **L**^{(norm)}(**0**) on . We may therefore conclude, just as in the first part of the proof, that equals up to a factor the Hessians of infinitely many eigenvalues of (a half of these factors is positive and the other half is negative). Denote by ** j** the vector which generates the discretization . Consider as a metric graph with the same connectivity as

*Γ*, but with as the set of its edge lengths. The

*k*-eigenvalues of are then described by where

*Σ*

_{α}={

**;**

*x**F*(

**;**

*x***)=0}. Namely the same torus, , can be used to describe the eigenvalues of**

*α**Γ*and , but with different flow directions (

**for**

*ξ**Γ*and

**for ). As for the spectral connection to , we know from theorem 2.3 that has the**

*j**k*-eigenvalues . Choose two

*k*-eigenvalues with different parity of

*p*, for example From a similar monotonicity argument, as in the first part of the proof, we get that 5.6where

*c*>0 and these Hessians are non-degenerate. Use relation (4.2) in lemma 4.3 to write As these Hessians are non-degenerate, we may choose neighbourhoods

*Ξ*

_{i}(

*i*=0,1) of

*k*

_{i}(

**0**)⋅

**on**

*j**Σ*

_{α}such that ∀

**∈**

*x**Ξ*

_{i}, is non-degenerate and define the corresponding Morse index function 5.7where returns the number of negative eigenvalues. Note that

*m*

_{j}is constant on each set

*Ξ*

_{i}, owing to non-degeneracy of the Hessians there. From (5.6), we get the following relation on these Hessians:

Let us now return to the original graph, *Γ*. The flow which characterizes its eigenvalues goes in the direction ** ξ** within the torus and we wish to adopt the definition of the Morse index function, (5.7), to this flow. We now show that

**⋅**

*j***∇**

*F*|

_{(x;0)}and

**⋅**

*ξ***∇**

*F*|

_{(x;0)}have the same sign on

*Ξ*

_{i}and conclude that As the flow defined by

**pierces both**

*ξ**Ξ*

_{0}and

*Ξ*

_{1}an infinite number of times, we get an infinite number of eigenvalues of

*Γ*whose Morse indices are

*σ*and

*β*−

*σ*. Applying theorem 2.1 finishes the proof.

All remains is therefore to show that ** j**⋅

**∇**

*F*|

_{(x;0)}and

**⋅**

*ξ***∇**

*F*|

_{(x;0)}have the same sign (for any which represents a simple eigenvalue). We have shown in the course of the proof of lemma 4.1 that

**⋅**

*j***∇**

*F*|

_{(x;0)}cannot vanish as

**represents a simple eigenvalue. We claim that this expression does not vanish even if we replace**

*x***j**with any convex linear combination of

**j**and

**. Namely we show that for all**

*ξ**t*∈[0,1], (

*t*

**+(1−**

*j**t*)

**)⋅**

*ξ***∇**

*F*|

_{(x;0)}≠0 from which it is clear that

**⋅**

*j***∇**

*F*|

_{(x;0)}and

**⋅**

*ξ***∇**

*F*|

_{(x;0)}have the same sign. Finally, the observation ∀

*t*∈[0,1], (

*t*

**+(1−**

*j**t*)

**)⋅**

*ξ***∇**

*F*|

_{(x;0)}≠0 is explained using the simplicity of the eigenvalue. The simplicity of the eigenvalue guarantees that

*Σ*

_{α}is homotopic to an |

*I*|−1 dimensional disc in a close neighbourhood of

**. For each**

*x**t*∈[0,1], the flow in the direction

*t*

**+(1−**

*j**t*)

**describes the eigenvalues of a certain metric graph. This is because is a vector of positive entries which is true as and have this property and the length map is linear (see (2.3)). At some point, the flow in the direction**

*ξ**t*

**+(1−**

*j**t*)

**will pierce**

*ξ**Σ*

_{α}at

**and generate an eigenvalue. If we had (**

*x**t*

**+(1−**

*j**t*)

**)⋅**

*ξ***∇**

*F*|

_{(x;0)}=0, this would mean that the flow is tangential to

*Σ*

_{α}(with

**being the touching point). This would allow for a slight perturbation of the direction of the flow in a way which would remove the relevant eigenvalue from the spectrum (or alternatively, would create a new one in its vicinity), which is not possible. □**

*x*

### Remark 5.4

This theorem can be compared with theorem 4.2, as their conclusions are similar. Yet, the current theorem seems weaker as it requires more conditions (see remark 5.3 for example). The proof, however, contains an element which allows one to bypass the need for symmetry (lemma 4.4) which is required in the proof of theorem 4.2, and thus gives the possibility to generalize this result to non-Neumann graphs and graphs with potentials. It was shown in [54] that theorem 2.3 holds also for *δ*-type conditions and for some electric potentials, if the the inverse Hill discriminant is used instead of the . Therefore, one might try to repeat the proof above, replacing the with the corresponding inverse Hill discriminant. The mechanism of ergodic flow on the torus does not describe accurately the eigenvalues of *δ*-type conditions, but it does so asymptotically, which should be enough for our purpose. The case of electric potential might be treated as well, as it was shown in recent work [57] that its spectrum can be described asymptotically by a secular function similar to (2.1).

## 6. Discussion

The main result of this paper, as is implied by its title, is the solution of the inverse nodal problem of determining a tree graph. The solution is similar for both metric and discrete graphs—the nodal point count sequence {0,1,2,3,…} may be possessed solely by tree graphs. The similarity between discrete and metric graphs carries over to the proofs—both use as a crucial tool the recently established connection between the graph's nodal count and the dependence of its eigenvalues on magnetic fields [26–28]. The proof for discrete graphs is based on a very basic observation—the trace of the operator does not depend on magnetic fields. The proof for the metric case is of more exploratory type and concerns properties of some individual eigenvalues. This proof yields some additional results and offers further investigative directions. Yet, it might seem superfluous for our main purpose. It would be interesting to develop an alternative proof for the metric inverse problem which tackles a specific spectral invariant similar to the discrete case. Possible candidates which arise as natural generalizations of the trace are the vacuum energy with some regularization, or the value of the zeta function at some point. Having said that, one should note that the proof of theorem 4.2 does include an implicit spectral invariant (see remark 4.5). This work also sets some restrictions on possible nodal count sequences which one can obtain from a graph. For example, we show that non-tree graphs cannot have a nodal count sequence which is almost like the tree nodal count (up to a finite number of discrepancies). In this sense, our result resembles a recent ‘quasi-isospectrality’ result by Rueckriemen [58]. He shows that if the spectra of two graphs agree everywhere aside from a sufficiently sparse set, then they are isospectral. In both his and our case, there are typical sequences (either nodal or spectral) which characterize the graphs and do not allow for ‘small’ number of discrepancies.

Putting aside the connection to the nodal count, one could phrase the results we obtained as purely magnetic properties of graphs' spectra; it is not possible for all graph eigenvalues to show diamagnetic behaviour (see [59], ch. 2). This statement holds for discrete graphs, whereas metric graphs obey an even stronger restriction—an infinite number of eigenvalues must violate the diamagnetic behaviour.

It is interesting to examine more deeply the genericity of the theorems 1.3 and 1.4. We have already claimed that assumption 1.1 is generic under various perturbations of the operator. Theorem 1.3 was indeed proved with quite a high generality by allowing a dense set of discrete Schrödinger operators. Yet, one may wish to restrict oneself to some particular classes of Laplacians (for example, the adjacency matrix, **C**=**D**−**D**^{1/2}**L****D**^{1/2}) and ask for which graphs does theorem 1.3 hold. This seems a rather involved question, which concerns a detailed study of the graph automorphism group (see [32], ch. 2 and references therein). In the case of metric graphs, the assumptions in theorems 1.4 and 4.2 seem milder than that in the discrete case as only a single generic eigenvalue is required. However, we restrict ourselves to Neumann vertex conditions and with no electric potentials. It is therefore desirable to generalize the current results to include other vertex conditions and potentials. A first step for doing so is suggested by the method of discretized versions of a graph presented in §5. See also remark 5.4 which offers a possible approach for such generalizations. Of particular interest is the question whether for a given metric graph, there is always some discretized version for which theorem 5.1 is not empty. If this is the case, theorem 5.1 might serve as an alternative to theorem 4.2 in the course of proof of the metric inverse result (theorem 1.4).

The inverse *nodal domain* count problem for metric graphs was solved as well in this paper, i.e. the nodal domain count sequence {1,2,3,…} implies the graph is a tree. Numerical evidence suggests that this should be the case for discrete graphs as well and it is interesting to prove (or maybe disprove) such an inverse result. A possible approach might be to check whether a similar magnetic–nodal connection exists for the nodal domain count as well (which would form a non-trivial generalization of other work [26–28]) and to apply it for the inverse problem. Another generalization direction of the magnetic–nodal link, from which inverse problems would benefit, is to give some treatment for non-simple eigenvalues and for eigenfunctions which vanish at vertices. This is highly relevant, as the frequently used discrete standard Laplacian tends to have such non-generic spectra.

Let us consider the inverse results in the paper from a spectral geometric viewpoint. We have managed to distinguish a graph with cycles from a tree by means of the nodal count. The next almost immediate problem would be to try and deduce the exact number of cycles out of the nodal count, if this is possible at all. We know that under generic assumptions, the number of cycles, *β*, is the upper bound of the nodal surplus. One would then inquire whether this bound is attained somewhere in the spectrum, i.e. whether
6.1In the discrete graphs setting, this is not the general case as shown by the following simple counter example.

The graph in figure 2 has *β*=2, yet its nodal point count is {0,2,3,3} (with respect to the given Laplacian matrix) and therefore . Note, however, that the nodal count depends not only on the graph, but also on the chosen Laplacian for it (within the possible models described in §1). For example, had we replaced the diagonal of the Laplacian with {4,3,2,1}, we would have obtained the nodal count {0,3,3,4}, which does attain the maximum in (6.1). We may therefore still wonder whether (6.1) holds within a certain class of Laplacians. If we consider the normalized Laplacian on the same graph, for example, we get that the eigenvalues are simple, but some eigenfunctions vanish at graph vertices and anyway (6.1) fails for the generic eigenvalues. The same is true for the so-called standard Laplacian as well (same Laplacian as above, but with the vertex degrees on its diagonal), where even not all eigenvalues are simple. This calls for appropriate definitions of the nodal count for non-generic eigenvalues and possible generalizations of theorem 2.1. The question of deducing *β* from the nodal count can be also asked for the metric graph setting. It is possible to show that indeed under a genericity assumption one may deduce the number of graph cycles out of the nodal count (by means other than in (6.1)). This is to be discussed in a future work, where the nodal surplus distribution of a metric graph is studied [60]. One should compare this inverse nodal problem to its analogous spectral one—whether the spectrum reveals the number of graph cycles. This is indeed the case, both for discrete graphs [61], lemma 4 and for metric graphs [62]. This comparison between the spectral data and the nodal data goes hand in hand with the aforementioned conjecture in [14] that nodal information resolves spectral ambiguity whenever it occurs. In the discrete graph example shown in figure 2, however, the information flow is in the opposite way than that of the conjecture—the spectrum stores some geometric information which the nodal count does not reveal. Yet, for metric graphs, as was mentioned here, both spectral and nodal sequences tell the number of graph cycles. Finally, we wish to mention trace formulae, which are a major tool for treating inverse problems, as they connect spectral information to geometry. For graphs, these formulae express spectral functions in terms of closed paths on the graph. A trace formula for the spectral counting function of a metric graph [50] was used to solve the inverse spectral problem on metric graphs [63]. It was suggested by Smilansky that similar trace formulae exist for functions of the nodal count and there is indeed some supporting evidence and derivations for specific classes of two-dimensional surfaces in [8,9,11], and progress on the problem for metric graphs in [10]. Yet, an exact trace formula for the nodal count has not been found yet. Such a formula will crucially advance solutions of inverse nodal problems of the kind presented in this paper and of many more.

## Funding statements

This work is supported by EPSRC grant no. EP/H028803/1.

## Acknowledgements

The author acknowledges Lennie Friedlander who proposed him the main inverse problem discussed in this paper. The author also cordially thanks Uzy Smilansky for numerous discussions of inverse nodal problems and for his continuous encouragement. The ingenious insights offered by Gregory Berkolaiko and Konstantin Pankrashkin are highly appreciated. The author greatly benefited from discussions with Jon Keating, Michael Levitin, Idan Oren and Adam Sawicki. The comments and corrections offered by Gregory Berkolaiko and Tracy Weyand on the final version helped to substantially improve the paper.

## Footnotes

One contribution of 13 to a Theo Murphy Meeting Issue ‘Complex patterns in wave functions: drums, graphs and disorder’.

- © 2013 The Author(s) Published by the Royal Society. All rights reserved.