{'fraction_non_alphanumeric': 0.045461873287119134, 'fraction_numerical': 0.011016174969100973, 'mean_word_length': 3.9731427044361305, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dependence of the spectrum of a quantum graph on vertex conditions and edge lengths

We study the dependence of the quantum graph Hamiltonian, its resolvent, and its spectrum on the vertex conditions and graph edge lengths. In particular, several results on the interlacing (bracketing) of the spectra of graphs with different vertex conditions are obtained and their applications are discussed.


Introduction
Graph models have long been used as a simpler setting to study complicated phenomena. Quantum graphs in particular have recently gained popularity as models for thin wires, eigenvalue statistics of chaotic systems and properties of the nodal domains of eigenfunctions. We refer the interested reader to the recent reviews [10,17,19] and collections of papers [3,7].
A quantum graph is a metric graph equipped with a self-adjoint differential "Hamiltonian" operator (usually of Schrödinger type) defined on the edges and matching conditions specified at the vertices. Every edge of the graph has a length assigned to it. In this manuscript we establish several results concerning the general properties of the spectrum of the Hamiltonian as a function of the parameters involved: the edge lengths and matching (vertex) conditions. In Section 2 we introduce the standard notions related to quantum graphs, vertex conditions, and quadratic forms of the corresponding Hamiltonians. The most widely used example of the vertex conditions, the δ-type condition, is described in some detail. The results presented in Section 3 concern the analyticity of the spectrum as a function of the parameters involved: vertex conditions and edge lengths. Analytic dependence on the potential (as an infinite-dimensional parameter) can also be established by the methods used in the Section, but we omit this to keep the presentation simple. In Section 4 we compute the derivative of an eigenvalue with respect to a variation in the length of an edge; this is an analogue of a well-known Hadamard variational formula. Derivative with respect to a parameter of a δ-type condition is also computed.
Section 5 again focuses on the δ-type condition at a vertex. Varying such a condition at a specified vertex or changing connectivity of the vertex we obtain families of spectra and study their interlacing properties. Eigenvalue interlacing (or bracketing) is a powerful tool in spectral theory with such wellknown applications as the derivation of the asymptotic Weyl law, see [5]. In the graph setting, it allows one to estimate eigenvalue of a given graph via the eigenvalues of its subgraphs, which may be easier to calculate. Interlacing results on graphs have already been used in several situations [2,21,26]. We significantly generalize these results and put them in the form particularly suited for the applications. We discuss several applications. In particular, we give a simple derivation of the number of nodal domains of the n-th eigenfunction on a quantum tree and study irreducibility of the spectrum of a family of graphs obtained by varying δ-type condition at one of the vertices.

Quantum graph Hamiltonian
Let Γ = (V, E) be a graph with finite sets of vertices V = {v j } and edges E = {e j }. We will assume that Γ is a metric graph, i.e. every edge e is a 1-dimensional segment with a positive finite length L e and a coordinate x e assigned. Each edge corresponds to two directed edges, or bonds, of opposite directions. If bonds b 1 and b 2 correspond to the same edge, they are called reversals of each other. In this case we use the notations b 1 = b 2 and b 2 = b 1 . A bond b inherits its length from the edge e it corresponds to, in particular, L b = L b = L e . A coordinate x b is assigned on each bond, and the coordinates on mutually reversed bonds are connected via Definition 2.1.
• The space L 2 (Γ) on Γ consists of functions that are measurable and square integrable on each edge e with the norm In other words, L 2 (Γ) is the orthogonal direct sum of spaces L 2 (e). • We denote by H k (Γ) the space which consists of the functions f on Γ that on each edge e belong to the Sobolev space H k (e) and is equipped with the norm • The Sobolev space H 1 (Γ) consists of all continuous functions from H 1 (Γ).
Note that in the definition of H k (Γ) the smoothness is enforced along edges only, without any junction conditions at the vertices at all. The continuity condition imposed on functions from the Sobolev space H 1 (Γ) means that any function f from this space assumes the same value at a vertex v on all edges adjacent to v, and thus f (v) is uniquely defined. This is a natural condition for onedimensional H 1 -functions, which are known to be continuous in the standard 1-dimensional setting.
A metric graph becomes quantum after being equipped with an additional structure: assignment of a self-adjoint differential operator. This operator will be also called the Hamiltonian. The frequently arising in the quantum graph studies operator is the negative second derivative acting on each edge (x is the coordinate x along an edge) or the more general Schrödinger operator where V (x) is an electric potential . (Our results will hold, for instance, for V ∈ L 2 (Γ). Generalizations to more general operators, e.g. including magnetic terms, are also straightforward.) Notice that for both these operators the direction of the edge is irrelevant. This is not true anymore if one wants to include derivative term of an odd order, e.g. magnetic potential, but we shall not address such operators in the present note (see, e.g., [8,24] concerning these issues).
The natural smoothness requirement coming from the ODE theory is that f belongs to the Sobolev space H 2 (e) on each edge e. Appropriate boundary value conditions at the vertices (vertex conditions) still need to be added, which are considered in the next subsection.
2.1. Vertex conditions. We will briefly describe now the known descriptions of the vertex conditions that one can add to the differential expression (2) in order to create a self-adjoint operator (see, e.g., [8,13,16,18] for details).
Assume that the domain of the operator is a subspace of the Sobolev space H 2 (Γ) (see the references above for the justification of this assumption). Then the standard Sobolev trace theorem (e.g., [6]) implies that both the function f , f ∈ H 2 (e), and its first derivative have correctly defined values at the endpoints of the edge e. Thus, for a function f ∈ H 2 (Γ) and a vertex v we can define the column vectors F (v) and F ′ (v) has the maximal rank.

(5)
The matrix A v B * v is self-adjoint. and functions f from the domain of H satisfy the vertex conditions where I is the d v × d v identity matrix. C: For every vertex v of degree d v , there are three orthogonal (and mutually orthogonal) projectors P D,v , P N,v and P R,v := I − P D,v − P N,v (one or two projectors can be zero) acting in C dv and an invertible self-adjoint operator Λ v acting in the subspace P R,v C dv , such that functions f from the domain of H satisfy the vertex conditions 2.2. Quadratic form. To describe the quadratic form of the operator H, which is a self-adjoint realization of the Schrödinger operator (2) acting along each edge, the self-adjoint vertex conditions written in the form (C) of Theorem 2.2 are the most convenient. The following theorem is cited from [18].
Theorem 2.3. The quadratic form h of H is given as where , denotes the standard Hermitian inner product in C dim P R,v . The domain of this form consists of all functions f that belong to H 1 (e) on each edge e and satisfy at each vertex v the condition P D,v F = 0. Correspondingly, the sesqui-linear form of H is

2.3.
Examples of vertex conditions. In this paper we will often be dealing with the δ-type conditions which are defined at a vertex v as follows: , where for each vertex v, α v is a fixed number. One recognizes this condition as being an analog of the conditions one obtains for the Schrödinger operator on the line with a δ potential. The special case α v = 0 is known as the Neumann (or Kirchhoff) condition.
The δ-type condition can be written in the form (6) with Since the self-adjointness condition (5) is satisfied if and only if α v is real. In order to write the vertex conditions in the form (8), one introduces the orthogonal projection P D,v onto the kernel of B v , the projector P R,v = I − P D,v and the self-adjoint operator Λ v = B A v on the range of P R,v . A straightforward calculation shows that P R,v is the one-dimensional orthogonal projector onto the space of vectors with equal coordinates and thus the range of P D,v is spanned by the vectors r k , k = 1, ..., d v − 1, where r k has 1 as the k-th component, −1 as the next one, and zeros otherwise. Then Λ v becomes the multiplication by the number α v d v . In particular, the quadratic form of the operator H (assuming δ-type conditions on all vertices of the graph) is defined on f ∈ H 1 (Γ), which are automatically continuous, and so Vertex Dirichlet condition requires that the function vanishes at the vertex: f (v) = 0. At the first glance, it might look like it is significantly different from the δ-type conditions, but a closer inspection shows that this is not the case. Indeed, since the function must vanish when approaching the vertex from any edge, the vertex Dirichlet condition can be recast in the following form: Now one finds resemblance with (11), and indeed, if one divides the equality in (11) by α v and then takes the limit when α v → ∞, one arrives to (13). Hence, vertex Dirichlet condition seems to be the limit case of (11) when α v → ∞. We thus introduce the extended δ-type conditions by allowing α v = ∞. In order to avoid considering infinite values of α v , the two types of conditions can be also written in the form (14) cos Here γ v = 0 corresponds to the Neumann condition and γ v = π/2 corresponds to the Dirichlet one, with more general δ-type conditions in between. Usefulness of considering Dirichlet condition as a part of the family of δ-type conditions becomes clear in spectral theory, as will be illustrated, for instance, in Theorem 5.1. In fact, it will be convenient later on in this paper to rewrite the extended δ-type conditions (14) in the following form: where z belongs to the unit circle in the complex plane, i.e. |z| = 1.
Interpreting the Dirichlet condition in terms of the corresponding projectors, as in part C of Theorem 2.2, one notices that here P D,v = I and, correspondingly, To summarize, the quadratic form for a graph with the extended δ-type conditions (i.e., allowing α v = ∞) at all vertices, can be written as (16) h Vertex Dirichlet condition is an example of a decoupling condition, since it essentially removes any connection between the edges attached to the vertex. Another example that will be useful to us is P R,v = I, P N,v = P D,v = 0 and Λ v = diag(α 1 , . . . , α dv ). In this case the function is no longer required to be continuous at the vertex and the condition reduces to 3. Dependence on vertex conditions and edge lengths 3.1. Dependence of the Hamiltonian. In this section, we discuss the (analytic) dependence of the quantum graph Hamiltonian H on the vertex conditions and the edge lengths. This issue happens to be important in many circumstances, e.g. when considering dependence of the spectrum and the eigenfunctions. To keep the notation simpler, we only address the case V ≡ 0. However, the results can be extended to non-zero electric potentials without any change in the proofs. In fact, the dependence on the potential is also analytic, so the potential can be added to the vertex conditions and edge length as an extra (infinite-dimensional) parameter.
As before, the graph Γ is assumed to be finite (i.e., it has finitely many vertices and finite lengths edges).
It will be convenient here to consider the vertex conditions in the form of (6):

Given a set of matrices
Then A can be considered as a block-diagonal matrix of the size The space of such complex matrices A can be identified with C 2 v d 2 v , or just C 2q , where we will use the shorthand notation We now define the sub-set U of C 2q that consists of matrices A satisfying the maximal rank condition (4) for each v ∈ V: We denote by U s the subset of U consisting of matrices satisfying the self-adjointness condition (5): The following statement describes some simple properties of these sets: U is an open and everywhere dense domain of holomorphy in C 2q .
Proof. Algebraicity of the set C 2q \ U is clear, since its elements are described by the algebraic relations forcing the highest order minors to vanish. This proves the first statement of the Lemma. The second claim is an immediate corollary of the first one, if one can show that U is not empty. This is done by noticing that A := (I 0) ∈ U.
Let us now return to the quantum graph Hamiltonian. Since we are going to look into its dependence on vertex conditions, we introduce the corresponding notation: Definition 3.2. The operator −d 2 /dx 2 defined on functions from H 2 (Γ) satisfying (6) at each vertex v is denoted by H A .
As we have already seen, the domain D(H A ) of the operator H A is a closed subspace D A of H 2 (Γ) that can be described as follows: In other words, D A is the kernel of the continuous linear operator where (17) T This simple observation allows us to establish nice behavior of the domain of H A with respect to the vertex conditions matrix A. In order to do this, let us start with a simple lemma: Proof. Indeed, according to (17), the function is in fact linear, and thus analytic with respect to A. Also, the set of vectors {F (v), F ′ (v)}| v∈V achievable from elements f of ⊕ e H 2 (e) is clearly arbitrary. Then, if the maximal rank condition is satisfied, this implies the surjectivity of T A .
Let us consider the trivial vector bundle over U with fibers equal to H 2 (Γ). Consider the sub-set In other words, we look at the domain D A of the operator H A as a "rotating" with A subspace of H 2 (Γ). The next results shows that this domain rotates "nicely" (analytically) with A and is topologically and analytically trivial as a vector bundle.
(1) D is an analytic sub-bundle of co-dimension 2E of the ambient trivial bundle. Proof. The first statement of the Theorem is local. So, let us pick a matrix A 0 ∈ U. According to Lemma 3.3, the operator T A 0 is surjective, and thus has a continuous right inverse R. Thus, is a projector onto the kernel of T A , i.e. on D A . Since this projector, by construction, is analytic with respect to A in a neighborhood of A 0 , this proves a part of the first claim of the theorem: D is an analytic Hilbert sub-bundle (e.g., [27]). It only remains to notice that co-dimension of the kernel of T A is the dimension of its range, i.e. 2E.
To prove the second claim, we notice that D is an infinite dimensional analytic Hilbert bundle. Due to the Kuiper's theorem on contractibility of the general linear group of any infinite-dimensional Hilbert space [20], all such bundles are topologically trivial. Since the base U is holomorphically convex, the Bungart's theorem [4] says that the same holds in the analytic category (see further discussion of the technique and relevant references in the survey [27]).
Let us prove the third claim. Since H A is the restriction to D A of the fixed operator −d 2 /dx 2 (with no vertex conditions attached), acting continuously from H 2 (Γ) to L 2 (Γ), the operator-function in question can be written as (−d 2 /dx 2 )T (A) and thus is analytic. The Fredholm property and the zero value of the index follow from [8,Theorem 14].

3.2.
Dependence of the resolvent. We now consider the question about the dependence on vertex conditions of the resolvent of H A . In order to do so, we need to consider the operator family H A − iI, where I denotes the identity operator in L 2 (Γ). Sobolev's compactness of embedding theorem shows that I is a compact operator from H 2 (Γ) to L 2 (Γ). This and the previous theorem imply that H A −iI is also an analytic family of Fredholm operators of zero index.
As analytic Fredholm theorem (see Appendix A) shows, the set Σ of the matrices A for which the operator H A − iI : D A → L 2 (Γ) is not continuously invertible, is principal analytic (i.e., can be given by an equation φ(A) = 0, where function φ is analytic). Since this set Σ does not include any points A of U s (because in this case the operator H A is self-adjoint), this singular set is nowhere dense. Proof. Analyticity of the inverse to an analytic family of bounded invertible operators is well known (e.g., [15,27]). Thus, (H A − iI) −1 is an analytic family of operators from L 2 (Γ) to H 2 (Γ), and thus also as a family of operators acting in L 2 (Γ). However, considered as operators in L 2 , they factor through the compact embedding of D A into L 2 (Γ), and thus are compact.

3.3.
Variations in the edge lengths. Sometimes one needs to consider the quantum graph's dependence on the variations in the edge lengths parameters {L e } (without changing graph's topology). We thus extend the previous considerations to include the dependence on the vector in fact, we allow "complex values of lengths" L, i.e. L ∈ (C \ {0}) E .
Let Γ be a quantum graph with the Hamiltonian We would like to vary the lengths of the edges (independently from each other), without changing topology or vertex conditions. Let us consider the vector ξ = {ξ e } ∈ (R + ) E of dilation factors along each edge. It is clear that such a dilation is equivalent to keeping the metric graph structure the same, while replacing Notice that this rescaling allows for "complex lengths" of the edges. This is useful, when considering analytic properties of the Hamiltonian with respect to the parameters.
The same arguments as in proving Theorem 3.4 lead to the following statement: Theorem 3.7.
(1) The bundle D over U × (C \ {0}) E with the fiber over (A, ξ) defined by the vertex condition matrix A ξ , is an analytic sub-bundle of co-dimension 2E of the ambient trivial bundle are Fredholm operators of index zero from H to L 2 (Γ).

3.4.
Dependence of the spectrum on the vertex conditions. In this section, we will derive some basic facts about relations between the quantum graph eigenvalues and continuous graph parameters (such as matrices A = {(A v b v )}| v∈V of vertex conditions and edges' lengths {L e }| e∈E . We denote by H A the operator −d 2 /dx 2 on a compact graph Γ with the domain described by the vertex conditions (6) that correspond to the matrix is maximal for any vertex v. We will also use notation H A,ξ for the re-scaled version of H A that acts as −ξ −2 d 2 /dx 2 e on the domain described by is the vector of (non-zero) scaling factors applied on each edge.
We are interested in the dependence of the spectrum of H A,ξ on the parameters (A, ξ) ⊂ U × (C \ {0}) E . Thus, we consider the operator pencil H A,ξ − λI of unbounded operators in L 2 (Γ).
The following result, which addresses analytic behavior of the spectrum, follows from Theorem 3.7 and the analytic Fredholm theorem (Appendix A) and [27,Theorem 4.11].
(1) The set S of all vectors such that H A,ξ − λI does not have a bounded inverse in L 2 (Γ), is principal analytic. Namely, there exists a non-zero function Φ(A, ξ, λ) analytic in U ×(C\{0}) E ×C, such that S coincides with the set of its zeros. (2) For any integer k ≥ 1, the set S k of all vectors • The set S is the graph of the multiple-valued function (A, ξ) → σ(H A,ξ ), and can be considered as a kind of "dispersion relation." Here σ(H) denotes the spectrum of the operator H.
• The sets S k are clearly nested: S k+1 ⊂ S k . Moreover, S 1 = S.
• For A ∈ U s (i.e., satisfying the condition guaranteeing self-adjointness of H A ) and ξ ∈ (R \ {0}) E , the operator H A,ξ is selfadjoint and its spectrum is real and discrete.
3.5. Eigenfunction dependence. We present here, for completeness, a simple and well known consequence of perturbation theory.
Theorem 3.10. The kernel Ker (H A,ξ − λI) forms a holomorphic k-dimensional vector bundle over the set S k \ S k+1 . In other words, if one has an local analytic eigenvalue branch λ(A, ξ) of constant multiplicity k, then, at least locally, one can choose an analytic basis of k eigenfunctions.
Proof. The spectral projector onto the corresponding spectral subspace is clearly analytic with respect to the parameter.

An Hadamard type formula
Hadamard's variational formulas [9,12,14,22] deal with the variation of the spectral data with respect to the domain perturbation. For simplicity, we will consider the case of variation of the eigenvalues with respect to a change in a "loose" edge's length. Namely, the end of the edge is assumed to be a vertex of degree 1 and the length of the edge will be denoted by s. We will also use s to denote the vertex of degree 1. The proof follows the well established pattern (see, e.g. [11]) and can be easily generalized.
where f ′ (s) is the value of the derivative of the eigenfunction at the end-vertex.
Proof. First we remark that by preceding theorems we can differentiate both the eigenvalue and the eigenfunction. We will omit the subscript s of f unless we want to highlight the dependence of the eigenfunction on s.
The Dirichlet condition at the vertex s has the form f s (s) = 0.
Differentiating it with respect to s we get (19) ∂f ∂s On the other hand, the eigenfunction is   (19) and (20) to get Substituting the last equation and the Dirichlet condition into (21) yields the desired result.
One can obtain similar results when varying vertex conditions rather than the length. For simplicity we only consider the δ-type vertex conditions. Proposition 4.2. Let λ = λ(α) be a simple eigenvalue of a graph Γ which satisfies δ-type vertex condition at v with the parameter α = ∞. Then If we re-parameterize the conditions at v as now allowing Dirichlet (ζ = 0) and excluding Neumann (ζ = ∞) conditions, the derivative is Proof. The proof follows the pattern of the proof of Proposition 4.1 with minor modifications. We deal with α-derivative first. The derivative of the normalization condition is now Taking the derivative of the quadratic form, see (12), yields Integrating by parts inside the sesqui-linear form h and collecting together all the "boundary" terms at v, we get where we used the δ-type condition at the vertex v. Now we use Hf = λf and the derivative of the normalization condition to get 2 Re h f, ∂f ∂α = 0, and, therefore, To deal with the Dirichlet case, we calculate, for α = 0 and ζ = 0, using condition (23) in the last step. Since λ(ζ) is an analytic function, the value of the derivative at ζ = 0 now follows by continuity.

Eigenvalue interlacing
We will be assuming that the Hamiltonian H is −d 2 /dx 2 +V (x) with the vertex conditions specified in the results. The eigenvalues λ n of H (also referred to as the eigenvalues of the graph and denoted λ n (Γ)) are labeled in non-decreasing order, counting their multiplicity.
The first theorem of this section describes the effect of modifying the vertex condition at a single vertex. We denote by Γ α a compact (not necessarily connected) quantum graph with a distinguished vertex v. Arbitrary self-adjoint conditions are fixed at all vertices other than v, while v is endowed with the δ-type condition with coefficient α: Theorem 5.1. Let Γ α ′ be the graph obtained from the graph Γ α by changing the coefficient of the condition at vertex v from α to α ′ . If −∞ < α < α ′ ≤ ∞ (where α ′ = ∞ corresponds to the Dirichlet condition, see section 2.3), then If the eigenvalue λ n (Γ α ′ ) is simple and it's eigenfunction f is such that either f (v) or f ′ (v) is non-zero then the inequalities can be made strict, (26) λ n (Γ α ) < λ n (Γ α ′ ) < λ n+1 (Γ α ).
Proof. The case of strict inequalities follows simply from the positivity of the derivative of λ n (Γ α ′ ) with respect to the parameter of the vertex condition, Proposition 4.2. For the possibly degenerate case we directly use the monotonicity of the quadratic form and rank-one nature of the perturbation. Denoting by Γ ∞ the graph with the Dirichlet condition at the vertex v, we will actually prove the chain of inequalities which is obviously equivalent to inequality (25). Since we are now considering the Dirichlet case separately, we will assume that α ′ = ∞. Consider the quadratic forms h α , h α ′ and h ∞ of the corresponding Hamiltonians. According to the discussion in section 2.3, we have on the appropriate subspaces of H 1 (Γ)(= e∈E H 1 (e)). In fact, All inequalities follow from the min-max description of the eigenvalues, namely (28) λ n = min The first inequality in (27) follows immediately from the observation that h α ′ ≥ h α for all f .
The domain D(h ∞ ) is smaller than D(h α ′ ) and the forms h ∞ and h α ′ agree on D(h ∞ ). Minimization over a smaller space results in a larger result, implying the second inequality in (27).
The last inequality follows from the fact that D(h ∞ ) is a co-dimension one subspace of D(h α ′ ). To provide more detail, let the minimum for λ n+1 (Γ α ) be achieved on the subspace Y (which is the span of the first n + 1 eigenvectors) of dimension n + 1. Then there is a subspace Y ∞ of dimension n, such that Y ∞ ⊂ Y and Y ∞ ⊂ D(h ∞ ). Then This is precisely the last needed inequality.
This theorem allows us to prove a simple but useful criterion for the simplicity of the spectrum of a tree.
Corollary 5.2. Let T be a tree with a δ-type condition at every internal vertex and an extended δ-type condition at every vertex of degree 1. If the eigenvalue λ of T has an eigenfunction that is non-zero on all internal vertices of T , then λ is simple.
Equivalently, if an eigenvalue λ of the tree T is multiple, there is an internal vertex v such that all functions from the eigenspace of λ vanish on v.
Proof. The two statements are almost contrapositives of each other, modulo the following observation: if for every internal vertex there is an eigenfunction that is non-zero on it, one can construct an eigenfunction which is non-zero on all internal vertices. Indeed, if m is the dimension of the eigenspace of λ, then the subspace of the eigenfunctions vanishing on any given v is at most m − 1. A finite union of subspaces of dimension m − 1 cannot cover the entire eigenspace.
We will work by induction on the number of internal vertices. If a tree has no internal vertices, it is an interval and there is nothing to prove since all eigenvalues are simple.
Assume the contrary: there is an eigenfunction f which is not zero on all internal vertices of the tree, but λ is not simple. Take an arbitrary internal vertex v and another eigenfunction g. Cutting the tree at the vertex v we obtain d v subtrees. On at least one of them the function g is not identically zero and not a multiple of f . Let T ′ be a such a subtree.
The next theorem deals with the modification of the structure of the graph by gluing a pair of vertices together. Let Γ ′ be the graph obtained from Γ by gluing the vertices v 0 and v 1 together into a single vertex v, so that E v = E v 0 ∪ E v 1 , and endowed with the δ-type condition Then the eigenvalues of the two graphs satisfy the inequalities Proof. Similarly to the proof of Theorem 5.1, we consider the quadratic forms of the two graphs and observe that they are defined by exactly the same expression (see section 2.3). However, joining the vertices together imposes an additional restriction on the domain of the quadratic form of the graph Γ ′ , namely is a co-dimension one subspace of D(h) and the rest of the proof is identical to the proofs of the second and third inequalities in (27).
Notice that if the domain of h ′ had co-dimension k, then one would have obtained by applying the same argument the inequality λ n (Γ) ≤ λ n (Γ ′ ) ≤ λ n+k (Γ). This observation immediately leads to the following generalization of Theorem 5.3: Theorem 5.4. Let the graph Γ ′ be obtained from Γ by k identifications, for example by gluing vertices v 0 , v 1 , . . . v k into one, or pairwise gluing of k pairs of vertices. Each identification results also in adding parameters α j in the vertex δ-type conditions, as in (29). Then This statement can be also proved by the repeated application of Theorem 5.3.
Remark 5.5. Theorem 5.1 applied to the case α ′ = ∞ is also a result about joining d v vertices together, since the vertex Dirichlet condition has the effect of disconnecting the edges at the vertex. Note the difference with the result in Theorem 5.4: the eigenvalues of the joined graph are now shifted down, but not further than the next eigenvalue of Γ, which contrasts with the weaker "not further than k-th next eigenvalue" result of the Theorem 5.4.
6. Some applications 6.1. Dependence of the spectrum on the coupling constant α at one vertex. As in section 5 we consider the family of compact graphs Γ α with a distinguished vertex v. Arbitrary self-adjoint conditions are fixed at all vertices other than v, while v is endowed with the δ-type condition with coefficient α: f is continuous at v and e∈Ev df dxe (v) = αf (v). We will be using the second condition in the form where |z| = 1. The Dirichlet condition corresponds to z = −1, while the Neumann-Kirchhoff corresponds to z = 1. We denote by H(z) the operator with the above condition at v and the previously fixed set of conditions at all other vertices. Then main result of this section is representation of the spectrum of this operator as the range at z of an irreducible multiple valued analytic function defined near the unit circle, plus a fixed discrete set, see Fig. 1.

Re z
Im z λ Figure 1. Spectrum of a graph as a function of the parameter z, which controls the matching condition of the form (32) at one of the vertices of the graph. The figure shows the non-decreasing function Λ(z) spiraling upwards and one of the constant branches from the set ∆. Theorem 6.1. There exist a bounded from below discrete set ∆ ∈ R and a multiple valued function Λ(z) ("dispersion relation") analytic in a neighborhood of the unit circle S 1 and real on S 1 , such that: (1) For any z ∈ S 1 , one has where σ(A) denotes the spectrum of the operator A. Proof. Notice that, as we already know, for each z ∈ S 1 , H(z) is a bounded from below self-adjoint operator with a discrete spectrum. Let λ n (z) be its nth eigenvalue, counted with multiplicity in non-decreasing order. Then, according to the perturbation theory, it is continuous on the unit circle cut at z = −1, where one can observe that the ground state λ 1 has an one-side limit equal to −∞.
(1) The function λ n (z) is non-decreasing in the counter-clockwise direction on the unit circle.
(2) There exists a function F (λ, z) analytic in a neighborhood of the unit circle S 1 such that λ ∈ σ(H(z)) if and only if F (λ, z) = 0.
Indeed, the first claim of the Lemma is a rephrasing of a part of Theorem 5.1 (and, essentially, a consequence of monotonicity of the quadratic form (16) with respect to α). The second claim is a direct consequence of Theorem 3.8.
Indeed, if the eigenspace of H(z) corresponding to λ is more than one-dimensional, then it contains an eigenfunction vanishing at the vertex v. Then, assuming z = −1, we conclude from (32) that the sum of derivatives is zero as well. Therefore this eigenfunction works for any point z ∈ S 1 . In the case z = −1 we select an eigenfunction with vanishing sum of derivatives at v and it automatically vanishes at v since it satisfies the Dirichlet condition.
Let now λ ∈ σ(H(z 1 )) σ(H(z 2 )) with the corresponding eigenfunctions f 1 and f 2 . Without loss of generality, z 1 = −1. First consider the case f 1 (v) = 0. Then, by Theorem 5.1, λ as an eigenvalue of H(z 1 ) lies strictly between consecutive eigenvalues of H(z 2 ) which contradicts our assumption. Thus f 1 (v) = 0 and the sum of derivatives of f 1 is zero by (32). We conclude that f 1 is an eigenfunction for any z ∈ S 1 thus completing the proof of the Lemma.
We now define the set ∆ as the set of all λ ∈ R such that λ ∈ σ(H(z)) for all z ∈ S 1 . As the previous lemma shows, one can describe ∆ as the intersection σ(H(−1)) σ(H(1)) of the Dirichlet and Neumann spectra and thus is discrete and bounded from below.
Consider now a neighborhood U in C of the circle S 1 and the set Σ that is the closure of the set To put things simply, we remove from the union of the spectra all "horizontal" branches (z, λ) with λ ∈ ∆. The second statement of Lemma 6.2 then implies that the set Σ is analytic. Moreover, for the neighborhood U being sufficiently small, it is a smooth complex analytic curve. Indeed, Lemma 6.3 implies that for all λ / ∈ ∆ the eigenvalues are simple, and thus the eigenvalue branch is analytic. Let now λ ∈ ∆ and (z 0 , λ) ∈ Σ for some z 0 ∈ S 1 . Then Lemma 6.3 says that the eigenvalue λ near z 0 either stays constant, or splits into the constant and possibly one or more increasing branches. The constant branches are excluded in the definition of Σ, equation (34). Also, there can be no more than one increasing branch, otherwise one would find two values of z with the same values of λ in Σ, which the lemma allows only to happen on horizontal branches. Moreover, as we have already concluded, the eigenvalue on such a branch must be simple. Then Rellich's theorem (e.g., [25,v.4,Theorem XII.3]) says that the increasing branch is analytic. We thus conclude that Σ consists of one or more non-intersecting analytic curves.
We will show now that there is only one component, if the neighborhood U is sufficiently small. First of all, the projection onto the λ-axis of S j (S 1 × R), where S j is any of the components of Σ is the whole real axis, otherwise the component whose projection does not cover the whole real axis would create an accumulation that would contradict the discreteness of the spectrum for each z ∈ S 1 . Then existence of two or more components would create equal eigenvalues for at least two distinct values of z, which would contradict to the Lemma 6.3.
Thus, Σ is an irreducible analytic curve that intersects each line {z} × R on the cylinder along the discrete spectrum σ(H(z)) and such that it is monotonically increasing counterclockwise. Hence, it forms a kind of a spiral winding around the cylinder infinitely many times when λ → ∞ and having a vertical asymptote when λ → −∞ (otherwise one would get a contradiction with the boundedness of each of the spectra from below). This proves the statement of the theorem. 6.2. Nodal count on trees. Here we present a simple proof of a result that was first discovered in [1,23,26]. With all ground-setting work done in Section 5 the proof is significantly shortened. Theorem 6.4. Let λ n be a simple eigenvalue of − d 2 dx 2 + V (x) on a tree graph Γ and its eigenfunction f (n) be non-zero at all vertices of Γ. Then f (n) has n − 1 zeros on Γ.
Proof. To simplify notation we will drop the script n when talking about the eigen-pair (λ n , f (n) ). We will prove the result by induction on the number of internal vertices of the tree Γ. If there are no internal vertices, Γ is simply an interval and the statement reduces to the classical Sturm's Oscillation Theorem (see, e.g. [5]).
Let v be a vertex of degree d v . Then v separates Γ into d v sub-trees Γ i , each with a strictly smaller number of internal vertices. For each subtree, the vertex v is a vertex of degree 1 with, so far, no vertex condition. We will impose δ-type condition with the parameter α i < ∞ chosen in such a way that the function f restricted to Γ i is still an eigenfunction. This value is simply α . The eigenfunction f still corresponds to the eigenvalue λ n which is still simple (otherwise we can construct another eigenfunction for the entire tree Γ, contradicting the simplicity of λ). It is an n i -th eigenvalue of Γ i and, applying the inductive hypothesis, we conclude that the function f has n i − 1 zeros on the subtree Γ i . Thus we need to understand the relationship between the numbers n i and the number n.
To do it, consider the subtree Γ i,∞ which now has Dirichlet condition on the vertex v. By Theorem 5.1, there are exactly n i − 1 eigenvalues of Γ i,∞ that are smaller than λ. Now consider the tree Γ ∞ , which is the original tree but with the Dirichlet condition at the vertex v. On one hand it has exactly n − 1 eigenvalues that are smaller than λ. On the other hand Γ ∞ is just a disjoint collection of subtrees Γ i,∞ and its spectrum is the superposition of the spectra of Γ i,∞ . Therefore the number of eigenvalues that are smaller than λ is Since we already proved that the number of zeros of f is equal to the sum on the right-hand side, we can conclude that µ(f ) = n − 1.
Theorem A.1. Let A(z) be an analytic family of Fredholm operators of index zero acting in a Banach space E, where z runs over a holomorphically convex domain Ω in C n (or a more general Stein analytic manifold). Then there exists an analytic function f (z) in Ω such that the set of all points z for which A(z) is not invertible coincides with the set of all zeros of the function f .
The proof of this statement can be found in many places, e.g. it follows from the Corollary to Theorem 4.11 in [27].