Proof. Fix a nodal domain \(U\) of \(f\). By the definition of nodal domain, \(\Omega_U\neq\emptyset\) and \(G_U[\Omega_U]\) is connected. Moreover, since \(\lambda\) is not the smallest eigenvalue, the eigenfunction \(f\) cannot be everywhere positive or everywhere negative. Then \(U\neq |K(G)|\). Take \(u\in \Omega_U\). If \(uv\) is an edge of \(G\) with \(v\in \Omega\setminus \Omega_U\) and \(f(v)\neq 0\), then \(uv\) is a sign-changing edge. Let \(z_{uv}\) be the unique zero point of \(\widetilde{f}\) on \(uv\). We have \[\begin{align} w_{uz_{uv}}=\frac{1}{l_{uz_{uv}}} =w_{uv}\frac{|f(u)-f(v)|}{|f(u)|}, \quad w_{vz_{uv}}=\frac{1}{l_{vz_{uv}}} =w_{uv}\frac{|f(u)-f(v)|}{|f(v)|}. \end{align}\] It follows that, for any \(u\in\Omega_U\), \[\begin{align} \lambda f(u)&=\frac{1}{m_u} \sum_{\substack{v\in V(G)\\ v\sim u}} w_{uv}\bigl(\widehat f(u)-\widehat f(v)\bigr)\\ &=\frac{1}{m_u} \sum_{\substack{v\sim u\\ v\in \Omega_U}} w_{uv}\bigl( f(u)- f(v)\bigr) + \frac{1}{m_u}\sum_{\substack{v\sim u\\ v\in B_U}} w_{uv}\bigl( f(u)-0\bigr)\\ &\quad + \frac{1}{m_u}\sum_{\substack{\widetilde{v}\sim u\\ \widetilde{v}\in B_U^0}} w_{u\widetilde{v}}\bigl( f(u)-\widetilde{f}(\widetilde{v})\bigr) + \frac{1}{m_u}\sum_{\substack{z_{uv}\sim u\\ z_{uv}\in \widetilde{B}_U^0}} w_{uz_{uv}}\bigl( f(u)-\widetilde{f}(z_{uv})\bigr)\\ &=\frac{1}{m_u} \sum_{\substack{y\in V(G_U)\\ y\sim u}} w_{uy}\bigl( \widetilde{f}(u)- \widetilde{f}(y)\bigr)=-\Delta_{\Omega_U}({G_U}) f(u). \end{align}\] Thus, \(\lambda\) is an eigenvalue of \(-\Delta_{\Omega_U}({G_U})\) and \(f|_{\Omega_U}\) is a Dirichlet eigenfunction of \(G_U\) with vanishing data on \(\partial_DG_U\). It remains to show that \(\lambda =\lambda_1(G_U,\partial_DG_U)\). Since \(U\) is a nodal domain, \(f\) has a fixed sign on \(\Omega_U\) and \(f(u)\neq 0\) for all \(u\in\Omega_U\). Then, by Proposition 7, we have \(\lambda_1(G_U,\partial_DG_U)=\lambda(G,B)\). The proof is complete. ◻

Proof. We first prove \(\sigma_s(e)<\sigma_s(f)\). Let \(s\geq 1\) and \(0<e<f\). By Lemma 4, \(\sigma_s(f)\) is simple and has a positive unit eigenvector \(\mathbf{x}=(x_1,\ldots,x_s)^\top\). Then \[\begin{align}\label{eq:T951} \sigma_s(f) &=\mathbf{x}^\top T_s(f)\mathbf{x}=\mathbf{x}^\top T_s(e)\mathbf{x}+(f-e)x_1^2\\ &\geq \sigma_s(e)+(f-e)x_1^2 >\sigma_s(e). \end{align}\tag{1}\]

Next we prove \(\sigma_{s+1}(i)<\sigma_s(j)\). Denote the positive unit eigenvector of \(\sigma_s(2)\) by \(\mathbf{y}=(y_1,\cdots,y_s)^\top\). Let \(\mathbf{z}^\top=(0,\mathbf{y}^\top)\). Then \[\begin{align} \sigma_{s+1}(i)<\mathbf{z}^\top T_{s+1}(i)\mathbf{z} =\mathbf{y}^\top T_s(2)\mathbf{y}=\sigma_s(2). \end{align}\] Combining this with 1 , we have \(\sigma_{s+1}(i)<\sigma_s(2)\leq \sigma_s(j)\). ◻

Proof. The proof is similar to the proof of Theorem 7, and we obtain a tree which is form of a comet \(C_{k,b}\) with \(f(v_k)>f(v_1)\), where \(f\) is a positive unit eigenfunction corresponding to \(\lambda_1(T)\). It remains to decide where the unique boundary edge of weight \(w\) is placed. We claim that this edge must be incident to \(v_1\). Suppose not, then the boundary edge of weight \(w\) is incident to \(v_k\). Denote this edge by \(v_0v_k\).

Construct a new weighted tree \(T'\) by replacing two boundary edges \(v_0v_k\) and \(v_1v_{k+1}\) with \(v_0v_1\) and \(v_kv_{k+1}\) respectively, where \(v_0v_1\) has weight \(w\) and \(v_kv_{k+1}\) has weight \(1\). Then \(T'\in \mathcal{T}_{k,b,w}\), and \[\begin{align} R_{T'}(f)-R_T(f) &= \left(f^2(v_k)+w f^2(v_1)\right) - \left(w f^2(v_k)+f^2(v_1)\right) \\ &= (w-1)\left(f^2(v_1)-f^2(v_k)\right) <0 . \end{align}\] Therefore \(\lambda_1(T')\leq R_{T'}(f)<R_T(f)=\lambda_1(T)\), which contradicts the Faber–Krahn property of \(T\). Hence \(T\cong C_{k,b}^{w}\). ◻

Proof of Theorem 1. Let \(B\) be the set of leaves. Let \(f\) be an eigenfunction corresponding to \(\lambda_2(T)\). Let \(U_1,\cdots,U_\ell\) be the nodal domains of \(f\), and let \(k_h=|\Omega_{U_h}|\) and \(b_h=|\partial_DG_{U_h}|\). Since \(f\) changes sign, we have \(\ell\geq 2\) Let \(w_h\geq 1\) be the weight of new boundary edge incident to \(\Omega_{U_h}\). By Theorem 6, for every \(h=1,\cdots,\ell\), \[\begin{align} \label{eq:nodal95lambda295all} \lambda_2(T)=\lambda_1(G_{U_h},\partial_DG_{U_h}). \end{align}\tag{2}\] Since each nodal domain has at least two Dirichlet boundary vertices, then by Lemma 8 and Theorem 7, we have \[\begin{align} \label{eq:basic95nodal95bound} \lambda_1(G_{U_h},\partial_DG_{U_h})\geq \sigma_{k_h}(b_h+w_h-1)\geq \sigma_{k_h}(b_h)\geq \sigma_{k_h}(2), \qquad h=1,\ldots,\ell . \end{align}\tag{3}\]

The proof is complete. ◻

Proof. Since \(G[\Omega_U]\) is a subgraph of \(G\), then \(\mathcal{A}_{\Omega_U}\mathrel{\vcenter{:}}= A(G[\Omega_U])-W_{\Omega_U}\). For convenience, we simply write \(\mathcal{A}_{\Omega_U} \mathrel{\vcenter{:}}= A-W\). We know that the eigenvalues \(\sigma_i\) of \(\mathcal{A}_{\Omega_U}\) are equivalent to \(\mu_i(G_U)\). Therefore, it suffices to prove the corresponding properties for \(\sigma_i\). Let \(s\geq \max\limits_{1\leq i\leq |\Omega_U|} W_{ii}\). Since \(\mathcal{A}_{\Omega_U}=(A-W+sI)-sI\), \((a)\) and \((b)\) follow directly from Lemma 4. The inequality in \((c)\) follows directly from Lemma 5. It remains to consider the equality condition. Let \(\boldsymbol{x}\) be a positive eigenfunction such that \(A\boldsymbol{x}=\sigma_1(A)\boldsymbol{x}, W\boldsymbol{x}=\sigma_1(W)\boldsymbol{x},\) and \((A-W)\boldsymbol{x}=\sigma_1(A-W)\boldsymbol{x}\). If \(\sigma_1(A-W)=\sigma_1(A)\), then \((A-W)\boldsymbol{x}= \sigma_1(A)\boldsymbol{x}-\sigma_1(W)\boldsymbol{x} =\sigma_1(A)\boldsymbol{x}\), which implies \(W=0\). It follows that the weights of all boundary edges of \(G_U\) vanish. ◻

Proof. Consider a nodal domain \(U\) of \(f\). By the definition of nodal domain, \(\Omega_U\neq\emptyset\) and \(G[\Omega_U]\) is connected. Moreover, since \(\rho\) is not the spectral radius of \(G\), the eigenfunction \(f\) cannot be everywhere positive or everywhere negative on \(V(G)\). Then \(U\neq |K(G)|\). Since \(G\) is connected, we have \(B_D(G_U)=\partial U\neq\emptyset\).

Take \(u\in\Omega_U\). If \(v\sim u\) and \(v\notin\Omega_U\), then there is a boundary vertex associated with the edge \(uv\). If \(f(v)=0\), this vertex is \(\tilde{v}\), and \[\begin{align} l_{u\tilde{v}}=l_{uv},\qquad w_{u\tilde{v}}=\frac{1}{l_{u\tilde{v}}}-\frac{1}{l_{uv}}=0. \end{align}\] If \(f(v)\neq 0\), this vertex is \(z_{uv}\). Since \(\widetilde{f}\) is linear on \(uv\) and \(\widetilde{f}(z_{uv})=0\), we have \(l_{u z_{uv}}=\frac{f(u)}{f(u)-f(v)}l_{uv}\), and \[\begin{align} w_{u z_{uv}} = \frac{1}{l_{u z_{uv}}}-\frac{1}{l_{uv}} = \frac{f(u)-f(v)}{f(u)}w_{uv}-w_{uv} = -\frac{w_{uv}f(v)}{f(u)}. \end{align}\]

Therefore, for any \(u\in\Omega_U\), \[\begin{align} \rho f(u) &= \sum_{v\sim u}w_{uv}f(v) = \sum_{v\sim u}w_{uv}\bigl(f(v)-f(u)\bigr) + \sum_{v\sim u}w_{uv}f(u) \\ &= \sum_{\substack{v\sim u\\ v\in\Omega_U}}w_{uv}\bigl(f(v)-f(u)\bigr) + \sum_{\substack{z_{uv}\sim u\\ z_{uv}\in\widetilde{B}_U^0}} w_{uv}\bigl(f(v)-f(u)\bigr) + \sum_{\substack{\tilde{v}\sim u\\ \tilde{v}\in B_U^0}} w_{uv}\bigl(0-f(u)\bigr) + \sum_{v\sim u}w_{uv}f(u) \\ &= \sum_{\substack{v\sim u\\ v\in\Omega_U}}w_{uv}\bigl(f(v)-f(u)\bigr) + \sum_{\substack{z_{uv}\sim u\\ z_{uv}\in\widetilde{B}_U^0}} w_{uv}\frac{-f(v)}{f(u)}\bigl(-f(u)\bigr) + \sum_{\substack{\tilde{v}\sim u\\ \tilde{v}\in B_U^0}} 0\cdot\bigl(-f(u)\bigr) + \sum_{\substack{v\sim u\\ v\in\Omega_U}}w_{uv}f(u) \\ &= \sum_{\substack{v\sim u\\ v\in\Omega_U}}w_{uv}\bigl(f(v)-f(u)\bigr) + \sum_{\substack{z_{uv}\sim u\\ z_{uv}\in\widetilde{B}_U^0}} w_{u z_{uv}}\bigl(-f(u)\bigr) + \sum_{\substack{\tilde{v}\sim u\\ \tilde{v}\in B_U^0}} w_{u\tilde{v}}\bigl(-f(u)\bigr) + \sum_{\substack{v\sim u\\ v\in\Omega_U}}w_{uv}f(u) \\ &= (\mathcal{A}_{\Omega_U} f)(u). \end{align}\] It follows that \(\rho\) is an eigenvalue of \(\mathcal{A}_{\Omega_U}\) and \(f|_{\Omega_U}\) is a Dirichlet adjacency eigenfunction of \(G_U\) with vanishing data on \(B_D(G_U)\). It remains to show that \(\rho=\mu_1(G_U)\). Since \(U\) is a nodal domain, \(f\) has a fixed sign on \(\Omega_U\) and \(f(u)\neq 0\) for all \(u\in\Omega_U\). Then, by Corollary 1, we have \(\mu_1(G_U)=\rho\).

The proof is complete. ◻

Proof of Theorem  2. We consider the connected case first. Let \(f\) be an eigenfunction corresponding to \(\rho_2(G)\). Choose a nodal domain \(U\) of \(f\) such that \(|\Omega_U|\) is minimum. Since \(\rho_2(G)\) is not the spectral radius, \(f\) changes sign. It follows that \(f\) has at least two nodal domains, and \(|\Omega_U|\leq \lfloor n/2\rfloor\). By Theorem 9, Corollary 1, and the fact that \(\alpha(s)\) is strictly increasing with respect to \(s\), we have \[\label{eq:nodal95chain} \begin{align} \rho_2(G) = \mu_1(G_U) \leq \rho_1(G[\Omega_U]) \leq \alpha(\lfloor n/2\rfloor). \end{align}\tag{7}\] Now we characterize the condition that the equality holds. The equality in the first inequality of 7 , by Corollary 1, implies that all boundary weights of \(G_U\) vanish. Therefore, every boundary vertex is a copy of some zero point of \(f\), which also implies that \(f\) has at least one zero point. The equality in the second inequality of 7 implies that \(\Omega_U\) is of the form \(G_1^*(\lfloor n/2\rfloor)\). Consider another nodal domain \(U'\neq U\). By Theorem 9, Corollary 1, we have \(\mu_1(G_{U'}) = \rho_2(G) = \alpha(\lfloor n/2\rfloor)\leq \rho_1(G[\Omega_{U'}])\). Since \(\alpha(s)\) is strictly increasing with respect to \(s\), \(|\Omega_{U'}| \geq \lfloor n/2\rfloor\). Since the existence of zero point, \(|\Omega_U|+|\Omega_{U'}|+1\leq n\). It follows that \(|\Omega_{U'}| = \lfloor n/2\rfloor\) and \(n\) is odd. Therefore, the graph is of the form \(G_1^*(\lfloor n/2\rfloor) \bullet K_1 \bullet G_2^*(\lfloor n/2\rfloor) \in \mathcal{C}\).

Conversely, suppose that \(n\) is odd and that \(G\) is obtained by joining a vertex to two such extremal graphs of order \(\lfloor n/2\rfloor\). Since the extremal graph need not be unique, write these two graphs as \(H_1\) and \(H_2\). The adjacency matrix of \(G\) has the form \[\begin{align} A(G)= \begin{pmatrix} A({H_1}) & 0 & {\boldsymbol{b}_1} \\ 0 & A({H_2}) & {\boldsymbol{b}_2} \\ {\boldsymbol{b}_1^{\top}} & {\boldsymbol{b}_2^{\top}} & 0 \end{pmatrix}. \end{align}\] Let \(\mathbf{u_i}\) be a Perron eigenvector of \(A({H_i})\) corresponding to \(\alpha(\lfloor n/2\rfloor)\) for \(i=1,2\). Choose constants \(c_1,c_2 \neq 0\), such that \(c_1 {\boldsymbol{b}_1^T} {\boldsymbol{u}_1}+c_2 {\boldsymbol{b}_2^T} {\boldsymbol{u}_2}=0\). Then \[\begin{align} A(G) \begin{pmatrix} c_1 {\boldsymbol{u}_1}\\ c_2 {\boldsymbol{u}_2}\\ 0 \end{pmatrix} = \begin{pmatrix} \alpha(\lfloor n/2\rfloor) c_1 {\boldsymbol{u}_1}\\ \alpha(\lfloor n/2\rfloor) c_2 {\boldsymbol{u}_2}\\ c_1 {\boldsymbol{b}_1^{\top}} {\boldsymbol{u}_1} + c_2 {\boldsymbol{b}_2^{\top}} {\boldsymbol{u}_2} \end{pmatrix} = \alpha(\lfloor n/2\rfloor) \begin{pmatrix} c_1 {\boldsymbol{u}_1}\\ c_2 {\boldsymbol{u}_2}\\ 0 \end{pmatrix}. \end{align}\] Thus \(\alpha(\lfloor n/2\rfloor)\) is an eigenvalue of \(G\). On the other hand, \(A({H_1})\oplus A({H_2})\) is a principal submatrix of \(A(G)\), and \(\rho_1(A({H_1})\oplus A({H_2}))=\alpha(\lfloor n/2\rfloor)\). By Lemma 6 , \(\rho_2(G)\leq \alpha(\lfloor n/2\rfloor)\). Moreover, since \(G\) is connected and properly contains both \(H_1\) and \(H_2\), we have \(\rho_1(G)>\alpha(\lfloor n/2\rfloor)\) by Lemma 9. Since \(\alpha(\lfloor n/2\rfloor)\) is an eigenvalue of \(G\), we conclude that \(\rho_2(G)=\alpha(\lfloor n/2\rfloor)\). This proves the connected equality case.

Now we remove the condition of connected graphs. Suppose that \(G\) is disconnected, and let \(H_1,\ldots,H_r\) be its connected components. The value \(\rho_2(G)\) is either \(\rho_2(H_k)\) for some \(k\) or the second largest number among \(\rho_1(H_1),\cdots,\rho_1(H_r)\). Combining this with the preceding discussion for the connected case, we obtain that, for each \(i\), \[\label{eq:nodal95chain952} \begin{align} \rho_2(H_i) \leq \alpha(\lfloor |V(H_i)|/2\rfloor) \leq \alpha(\lfloor n/2\rfloor). \end{align}\tag{8}\] Moreover, at most one component can have spectral radius larger than \(\alpha(\lfloor n/2\rfloor)\). Otherwise two components would both have order larger than \(\lfloor n/2\rfloor\), which is impossible for a graph of order \(n\). Therefore \(\rho_2(G) \leq \alpha(\lfloor n/2\rfloor)\).

If \(n\) is even and the equality holds, then \(\rho_2(G)\) cannot come from some \(\rho_2(H_k)\). Otherwise, since \(G\) is disconnected, then \(|V(H_k)|<n\), and we have \(\lfloor |V(H_k)|/2\rfloor<\lfloor n/2\rfloor\), which implies that \(\rho_2(H_k)\leq \alpha(\lfloor |V(H_k)|/2\rfloor)< \alpha( n/2)\). Thus equality comes from a component \(H_{i_1}\) with \(\rho_1(H_{i_1})=\alpha( n/2 )\). Since \(\rho_2(G)=\alpha( n/2)\), we have \(\rho_1(G)\geq \alpha( n/2 )\), which forces the spectral radius of another connected component \(H_{i_2}\) to be at least \(\alpha( n/2 )\). Since \(\alpha(s)\) is strictly increasing with respect to \(s\), components \(H_{i_1}\) and \(H_{i_2}\) have order \(n/2\). Therefore, the extremal graph is of the form \(G_1^*(n/2)\cup G_2^*(n/2)\). The converse follows immediately from the spectrum of a disjoint union.

If \(n\) is odd and the equality holds, then \(\rho_2(G)\) cannot come from some \(\rho_2(H_k)\). Indeed, if \(|V(H_k)|\leq 2\lfloor n/2\rfloor-1\), then the second inequality in inequality 8 is strict. If \(|V(H_k)|= 2\lfloor n/2\rfloor\), then \(\rho_2(H_k)<\alpha(\lfloor n/2\rfloor)\), as can be seen from the discussion of the connected case above. Hence \(\rho_2(H_i)<\alpha(\lfloor n/2\rfloor)\) for each component \(H_i\). Then equality must come from a component \(H_{j}\) with \(\rho_1(H_{j})=\alpha(\lfloor n/2 \rfloor)\). Denote the union of the remaining components by \(G_2\), and we have \(|V(G_2)|=\lceil n/2\rceil\). We claim that \(\rho_1(G_2)\geq \alpha(\lfloor n/2\rfloor)\). Indeed, if \(\rho_1(G_2)<\alpha(\lfloor n/2\rfloor)\), then \(\rho_2(G)=\max\{\rho_2(H_j),\rho_1(G_2)\}< \alpha(\lfloor n/2\rfloor)\), a contradiction. Therefore, the graph is of the form \(G_1^*(\lfloor n/2\rfloor)\cup G_2(\lceil n/2\rceil)\), where \(\rho_1(G_2(\lceil n/2\rceil))\geq \rho_1(G_1^*(\lfloor n/2\rfloor))\) and \(\rho_1(G_1^*(\lfloor n/2\rfloor))=\alpha(\lfloor n/2\rfloor)\). The converse is direct based on the monotonicity of \(\alpha(s)\).

By comparing the connected and disconnected cases, we obtain the complete equality condition. The proof is complete. ◻

Proof of Theorem 3. We first show that \(x_{u^*}=\min_{v\in V(G^*(t))}x_v\). Suppose, to the contrary, that there exists a vertex \(v\in V(G^*(t))\) such that \(x_v<x_{u^*}\). The pair \((G^*(t),v)\) is admissible in the definition of \(\beta(t)\). Then \[\begin{align} \beta(t) &\geq \sigma_1(A({G^*(t)})-I_{vv}) \geq \frac{\mathbf{x}^{\top}(A({G^*(t)})-I_{vv})\mathbf{x}}{\mathbf{x}^{\top}\mathbf{x}}= \frac{\mathbf{x}^{\top}(A({G^*(t)})-I_{u^*u^*})\mathbf{x}}{\mathbf{x}^{\top}\mathbf{x}} + \frac{x_{u^*}^2-x_v^2}{\mathbf{x}^{\top}\mathbf{x}} \\ &= \beta(t)+\frac{x_{u^*}^2-x_v^2}{\mathbf{x}^{\top}\mathbf{x}}>\beta(t), \end{align}\] a contradiction. Therefore, \(x_{u^*}=\min_{v\in V(G^*(t))}x_v\).

Next, we prove that \(\rho_2(G)\leq \beta(\frac{n}{2})\). Let \(G\in\mathcal{C}\) be a connected graph of order \(n\), and let \(f\) be a \(\rho_2(G)\)-eigenfunction. Hence \(f\) changes sign. Choose a nodal domain \(U\) of \(f\) such that \(|\Omega_U|\) is minimum. It follows that \(|\Omega_U|\leq n/2\). If \(|\Omega_U|<n/2\), then, by Corollary 1, Theorem 9, and \(\beta(n/2)>\alpha(s)\) for \(s<n/2\), we obtain \[\begin{align}\label{eq:U95n95even951} \rho_2(G) = \mu_1(G_U) \leq\rho_1(G[\Omega_U]) \leq \alpha(|\Omega_U|) < \beta(n/2). \end{align}\tag{9}\] If \(|\Omega_U|=n/2\), then \(f\) has exactly two nodal domains. Denote the other one by \(U'\). We have \(|\Omega_{U'}|=n/2\). Then, \(\{v\in V(G): f(v)=0\}=\emptyset\). Therefore, every boundary vertex of \(G_U\) and \(G_{U'}\) is produced by cutting a sign-changing edge between \(\Omega_U\) and \(\Omega_{U'}\).

Let \(\{a\in \Omega_U: N_{\Omega_{U'}}(a)\neq \emptyset\}=\{a_1,\ldots,a_p\}\). For each \(i\in\{1,\ldots,p\}\), write \(N_{\Omega_{U'}}(a_i)=\{b_{i1},\ldots,b_{iq_i}\}\). Then the set of edges of \(G\) joining the two nodal domains \(U\) and \(U'\) is \[\begin{align} E(G[\Omega_U],G[\Omega_{U'}])=\{a_i b_{ij}\in E(G): 1\leq i\leq p,\;1\leq j\leq q_i\}. \end{align}\] Since \(G\) is connected, \(E(G[\Omega_U],G[\Omega_{U'}])\neq \emptyset\), and we have \(\sum_{i=1}^{p}q_i\geq 1\).

Replacing \(f\) by \(-f\) if necessary, we may assume that \(f(a_i)>0>f(b_{ij})\) for all \(1\leq i\leq p\) and \(1\leq j\leq q_i\). For each pair \((i,j)\) with \(1\leq i\leq p\) and \(1\leq j\leq q_i\), let \(z_{ij}\) be the unique zero point of the edgewise linear extension \(\widetilde{f}\) on the edge \(a_i b_{ij}\). Then \(z_{ij}\) is a Dirichlet boundary vertex of both \(G_U\) and \(G_{U'}\). Since the original edge \(a_i b_{ij}\) has weight \(1\), its length is \(1\). By the linearity of \(\widetilde{f}\) on \(a_i b_{ij}\), we have \(l_{a_i z_{ij}}=\frac{f(a_i)}{f(a_i)-f(b_{ij})}\) and \(l_{b_{ij}z_{ij}}=\frac{-f(b_{ij})}{f(a_i)-f(b_{ij})}\). It follows by Definition 4 that \[w^{U}_{a_i z_{ij}}=\frac{1}{l_{a_i z_{ij}}}-1=\frac{f(a_i)-f(b_{ij})}{f(a_i)}-1=-\frac{f(b_{ij})}{f(a_i)}>0\] and \[w^{U'}_{b_{ij} z_{ij}}=\frac{1}{l_{b_{ij} z_{ij}}}-1=\frac{f(a_i)-f(b_{ij})}{-f(b_{ij})}-1=-\frac{f(a_i)}{f(b_{ij})}>0.\] Therefore, \[\begin{align} \sum_{v\in \Omega_U}(W_{\Omega_U})_{vv} = \sum_{i=1}^{p}\sum_{j=1}^{q_i}\left(-\frac{f(b_{ij})}{f(a_i)}\right), \quad \sum_{v\in \Omega_{U'}}(W_{\Omega_{U'}})_{vv} = \sum_{i=1}^{p}\sum_{j=1}^{q_i}\left(-\frac{f(b_{ij})}{f(a_i)}\right)^{-1}. \end{align}\] By the Cauchy–Schwarz inequality, \[\begin{align}\label{theta} \left(\sum_{v\in \Omega_U}(W_{\Omega_U})_{vv}\right) \left(\sum_{v\in \Omega_{U'}}(W_{\Omega_{U'}})_{vv}\right) & =\left(\sum_{i=1}^{p}\sum_{j=1}^{q_i} \left(-\frac{f(b_{ij})}{f(a_i)}\right)\right)\left(\sum_{i=1}^{p}\sum_{j=1}^{q_i}\left(-\frac{f(b_{ij} )}{f(a_i)}\right)^{-1}\right) \\ &\geq \left(\sum_{i=1}^{p}\sum_{j=1}^{q_i}1 \right )^2 =(\sum_{i=1}^{p}q_i)^2 \geq 1. \end{align}\tag{10}\] Consequently, \[\begin{align} \max\left\{ \sum_{v\in \Omega_U}(W_{\Omega_U})_{vv}, \sum_{v\in \Omega_{U'}}(W_{\Omega_{U'}})_{vv} \right\}\geq 1. \end{align}\] WLOG, let \(\sum_{v\in \Omega_U}(W_{\Omega_U})_{vv}\geq \sum_{v\in \Omega_{U'}}(W_{\Omega_{U'}})_{vv}\). Then \(\sum_{v\in \Omega_U}(W_{\Omega_U})_{vv} \geq 1\). Let \(\theta_U=\sum_{v\in \Omega_U}(W_{\Omega_U})_{vv}\). Let \(\boldsymbol{y}\) be the positive unit eigenvector corresponding to \(\sigma_1(A(G[\Omega_U])-W_{\Omega_U})\), and choose \(u\in \Omega_U\) such that \(y_u=\min_{v\in \Omega_U}y_v\). Then, we have \[\begin{align}\label{eq:n95even95D95A951} \sigma_1(A(G[\Omega_U])- I_{uu}) & \geq \mathbf{y^{\top}}(A(G[\Omega_U])-I_{uu})\mathbf{y}=\mathbf{y^{\top}}(A(G[\Omega_U])-W_{\Omega_U})\mathbf{y}+\sum_{v\in \Omega_U}(W_{\Omega_U})_{vv}y_v^2-y_u^2 \\ &\geq \mathbf{y^{\top}}(A(G[\Omega_U])-W_{\Omega_U})\mathbf{y}+\sum_{v\in \Omega_U}(W_{\Omega_U})_{vv}y_v^2-\theta_Uy_u^2 \\ &=\sigma_1(A(G[\Omega_U])-W_{\Omega_U}) +\sum_{v\in \Omega_U}(W_{\Omega_U})_{vv}(y_v^2-y_u^2) \\ &\geq \sigma_1(A(G[\Omega_U])-W_{\Omega_U}). \end{align}\tag{11}\] Since \(\sigma_1(A(G[\Omega_U])-W_{\Omega_U})=\mu_1(G_U)\), by Corollary 1, Theorem 9, and 11 , we have \[\begin{align} \rho_2(G) = \mu_1(G_U) =\sigma_1(A(G[\Omega_U])-W_{\Omega_U}) \leq \max_{v\in \Omega_U}\sigma_1(A(G[\Omega_U])-I_{vv}) \leq \beta(n/2). \end{align}\] Combining the two cases gives \(\rho_2(G)\leq \beta(n/2)\).

It remains to show that equality holds if and only if \(G\cong 2G^*(n/2)+u_1u_2\in \mathcal{C}\). Suppose that equality \(\rho_2(G)=\beta(n/2)\) holds for some connected graph \(G\in\mathcal{C}\) of order \(n\). By 9 , the case \(|\Omega_U|<n/2\) implies \(\rho_2(G)<\beta(n/2)\).

If \(|\Omega_U|=n/2\), then, as above, the nodal domains determined by \(f\) are exactly two, denoted by \(U\) and \(U'\). The equality also implies \(\max_{v\in \Omega_U}\sigma_1(A(G[\Omega_U])-I_{vv})=\beta(n/2)\). Moreover, 11 forces that \({\mathbf{y}}\) is an eigenvector corresponding to \(\sigma_1(A(G[\Omega_U])-I_{vv})\) for any \(v\in \Omega_U\), \(\sum_{v\in \Omega_U}(W_{\Omega_U})_{vv}(y_v^2-y_u^2) =0\), and \((\theta_U-1)y_u^2=0\). Hence \(\theta_U=1\). Let \(\theta_{U'}=\sum_{v\in \Omega_{U'}}(W_{\Omega_{U'}})_{vv}\). Since \(\theta_U=1\) and \(\theta_U=\max\{\theta_U,\theta_{U'}\}\), we have \(\theta_{U'}\leq 1\). It follows by 10 that \(\theta_{U'}= 1\), which implies that there is exactly one edge in \(E(\Omega_U,\Omega_{U'})\) because \((\sum_{i=1}^{p}q_i)^2 = 1\). Hence \(U\) and \(U'\) are linked by exactly one edge, denoted by \(u_1 u_2\), where \(u_1\in\Omega_U\) and \(u_2\in\Omega_{U'}\), and \(W_{\Omega_U}=I_{u_1u_1}\), \(W_{\Omega_{U'}}=I_{u_2u_2}\). Combining with \(\sum_{v\in \Omega_U}(W_{\Omega_U})_{vv}(y_v^2-y_u^2) =0\), we know that \(u_1\) is a vertex whose component of \(y\) has the smallest value and \(y\) is also a positive unit eigenvector corresponding to \(\sigma_1(A(G[\Omega_U])-I_{u_1u_1})\). The same argument applied to \(U'\) shows that \(u_2\) is a minimum-component vertex of the positive eigenvector corresponding to \(\sigma_1(A(G[\Omega_{U'}])-I_{u_2u_2})\). Since \(\rho_2(G)=\mu_1(G_U)=\mu_1(G_{U'})=\beta(n/2)\), we obtain \(\sigma_1(A(G[\Omega_U])-I_{u_1u_1})=\sigma_1(A(G[\Omega_{U'}])-I_{u_2u_2})=\beta(n/2)\). By the uniqueness assumption, \[\begin{align} (G[\Omega_U],u_1)\cong (G^*(n/2),u^*), \qquad (G[\Omega_{U'}],u_2)\cong (G^*(n/2),u^*). \end{align}\] Therefore \(G\cong 2G^*(n/2)+u_1u_2\).

Conversely, suppose that \(G\cong 2G^*(n/2)+u_1u_2\), where \(u_i\) is the copy of \(u^*\) in the \(i\)-th copy of \(G^*(n/2)\) for \(i=1,2\). Let \(H=G^*(n/2)\), and let \(\mathbf{x}>0\) be the positive unit eigenvector corresponding to \(\sigma_1(A(H)-I_{u^*u^*})=\beta(n/2)\). Thus \((A(H)-I_{u^*u^*})\mathbf{x}=\beta(n/2)\mathbf{x}\). Define a vector \(\boldsymbol{\xi}\) on \(G\) by \[\begin{align} \xi_v= \begin{cases} x_v, & v\in V(H_1),\\ -x_v, & v\in V(H_2), \end{cases} \end{align}\] where \(H_1\) and \(H_2\) are the two copies of \(H\). For every vertex \(v\neq u_1,u_2\), \((A(G)\boldsymbol{\xi})_v= (A(H)\mathbf{x})_v=\beta(n/2)\xi_v\). For \(u_1\), \[\begin{align} (A(G)\boldsymbol{\xi})_{u_1}=(A(H)\mathbf{x})_{u^*}-x_{u^*}=((A(H)-I_{u^*u^*})\mathbf{x})_{u^*}=\beta(n/2)x_{u^*} = \beta(n/2)\xi_{u_1}. \end{align}\] Similarly, we have \((A(G)\boldsymbol{\xi})_{u_2}=\beta(n/2)\xi_{u_2}\). Therefore, \(A(G)\boldsymbol{\xi}=\beta(n/2)\boldsymbol{\xi}\). Since \(\boldsymbol{\xi}\) changes sign and \(G\) is connected, \(\beta(n/2)\) is not the spectral radius of \(G\). Therefore, \(\rho_2(G)\geq \beta(n/2)\). On the other hand, by the upper bound already proved, we have \(\rho_2(G)\leq \beta(n/2)\). Thus \(\rho_2(G)=\beta(n/2)\). This proves the sufficiency.

In conclusion, the equality holds if and only if \(G\cong 2G^*(n/2)+u_1u_2\in \mathcal{C}\). The proof is complete. ◻

Proof. First we show that \(\alpha(r+1)>\alpha(r)\). Let \(H\in\mathcal{C}\) be a graph of order \(r\) such that \(\rho_1(H)=\alpha(r)\). Choose a connected component \(H_0\) of \(H\) such that \(\rho_1(H_0)=\rho_1(H)=\alpha(r)\). By the pendant-extension property, if we attach a new pendant vertex \(z\) to a vertex \(u\in V(H_0)\), then the resulting graph \(H'\) still belongs to \(\mathcal{C}\). Let \(H'_0\) be the connected component of \(H'\) containing \(H_0\cup\{z\}\). Then \(H_0\) is a proper subgraph of the connected graph \(H'_0\). By Lemma 9, \(\rho_1(H_0')>\rho_1(H_0)=\alpha(r)\). Therefore \(\alpha(r+1)\geq \rho_1(H')>\alpha(r)\).

Next, we prove \(\beta(r+1)>\alpha(r)\). Let \({\mathbf{x}}>{\mathbf 0}\) be the unit Perron vector of \(A({H_0})\) corresponding to \(\rho_1(H_0)=\alpha(r)\). For \(\varepsilon>0\), define a vector \({\mathbf{y}}\) on \(V(H_0)\cup\{z\}\) by \({\mathbf{y}}|_{V(H_0)}= {\mathbf{x}}\) and \(y_z=\varepsilon\). Hence \[{\mathbf{y}}^{\top}(A({H'_0})-I_{zz}){\mathbf{y}} = {\mathbf{x}}^{\top}A({H_0}) {\mathbf{x}}+2\varepsilon x_u-\varepsilon^2 = \alpha(r)+2\varepsilon x_u-\varepsilon^2.\] Since \({\mathbf{y}}^{\top} {\mathbf{y}}=1+\varepsilon^2\), we have \[\frac{ {\mathbf{y}}^{\top}(A({H'_0})-I_{zz}) {\mathbf{y}}}{ {\mathbf{y}}^{\top} {\mathbf{y}}} = \frac{\alpha(r)+2\varepsilon x_u-\varepsilon^2}{1+\varepsilon^2}.\] Choosing \(0<\varepsilon<2x_u/(\alpha(r)+1)\), we have \[\frac{ {\mathbf{y}}^{\top}(A({H'_0})-I_{zz}) {\mathbf{y}}}{ {\mathbf{y}}^{\top} {\mathbf{y}}}>\alpha(r).\] Thus \(\sigma_1(A({H'_0})-I_{zz})>\alpha(r).\) It follows that \(\beta(r+1)\geq \sigma_1(A({H'})-I_{zz})\geq \sigma_1(A({H'_0})-I_{zz}) >\alpha(r).\)

It remains to prove that \(\alpha(r)>\beta(r)\). Let \(G\in\mathcal{C}\) be a graph of order \(r\) consisting of connected components \(G_1,\ldots,G_q\), and choose \(u\in V(G_1)\). Then \[A(G)-I_{uu}=(A({G_1})-I_{uu})\oplus A({G_2})\oplus\cdots\oplus A({G_q}).\] If \(q\geq 2\), then \(\rho_1(G_i)\leq \alpha(|V(G_i)|)< \alpha(r).\) Since \(G_1\) is connected, by Lemma 4, the largest eigenvalue of \(A({G_1})-I_{uu}\) has a positive unit eigenvector, denoted by \({\mathbf{w}}\). Hence \[\begin{align}\label{component-upper-bound} \sigma_1(A({G_1})-I_{uu})={\mathbf{w}}^{\top}A({G_1}){\mathbf{w}} - w_u^2< {\mathbf{w}}^{\top}A({G_1}) {\mathbf{w}}\leq\rho_1(G_1) \leq\alpha(|V(G_1)|)\leq \alpha(r). \end{align}\tag{12}\] Therefore every block of \(A(G)-I_{uu}\) has largest eigenvalue strictly smaller than \(\alpha(r)\), and hence \(\sigma_1(A(G)-I_{uu}) < \alpha(r).\) Taking the maximum over all pairs \((G,u)\) gives \(\beta(r)<\alpha(r).\) If \(q=1\), then 12 still holds. It follows that \(\beta(r)<\alpha(r)\) for any \(q\geq 1\). Combining \(\alpha(r)>\beta(r)\) and \(\beta(r+1)>\alpha(r)\), we obtain the desired result. ◻

Proof. Since the complete graph uniquely attains the maximum spectral radius among all graphs of a given order, and \(\rho_1(K_s)=s-1< \rho_1(K_t)=t-1\) for \(s< t\), the corollary follows immediately from Theorem 2. ◻

Proof. Let \(\mathcal{C}\) be the class of connected graphs, which satisfies pendant-extension property. By Lemma 11, for any positive integers \(s<t\), we have \(\alpha(t)>\beta(t)>\alpha(s)>\beta(s)\). If \(n\) is odd, then the corollary follows immediately from Theorem 2. If \(n\) is even, then the corollary follows immediately from Theorem 3. ◻

Proof. Since the complete balanced bipartite graph uniquely attains the maximum spectral radius among all graphs of a given order, and \(\rho_1(K_{\lfloor \frac{s}{2}\rfloor,\lceil\frac{s}{2}\rceil} )= \sqrt{\lfloor \frac{s}{2}\rfloor\lceil\frac{s}{2}\rceil}< \rho_1(K_{\lfloor \frac{t}{2}\rfloor,\lceil\frac{t}{2}\rceil} )= \sqrt{\lfloor \frac{t}{2}\rfloor\lceil\frac{t}{2}\rceil}\) for \(s< t\), the corollary follows immediately from Theorem 2. ◻

Proof. Let \(\mathcal{C}\) be the class of trees, which satisfies pendant-extension property. By Lemma 11, for any positive integers \(s<t\), we have \(\alpha(t)>\beta(t)>\alpha(s)>\beta(s)\).

For odd \(n\), write \(n=2t+1\). By Theorem 2, we have \[\begin{align} \rho_2(T)\leq \alpha(t)=\rho_1(K_{1,t-1})=\sqrt{t-1} =\sqrt{\frac{n-3}{2}}. \end{align}\] The star uniquely attains the maximum spectral radius among all graphs of a given order by [39]. Theorem 2 shows that an extremal tree is obtained from two copies of \(K_{1,t-1}\) by gluing them through a vertex \(v^*\) with \(f(v^*)=0\). To ensure that the extremal graph remains a tree, \(v^*\) is adjacent to exactly one vertex in each copy of \(K_{1,t-1}\). Based on specific way of gluing (two attachment vertices are centers or leaves), we obtain exactly three extremal trees \(S^3_{t-1,t-1}\), \(S^4_{t-2,t-1}\), \(S^5_{t-2,t-2}\).

For even \(n\), write \(n=2t\). We claim that, for a leaf \(v'\) of \(K_{1,t-1}\), we have \(\beta(t)=\sigma_1(A({K_{1,t-1}})-I_{v'v'})\). Let \(T\) be a tree of order \(t\), \(v\in V(T)\), and let \(\mathbf{x}\) be a positive unit eigenvector of \(A(T)-I_{vv}\) corresponding to \(\sigma_1(A(T)-I_{vv})\). Choose vertices \(v_1\) and \(v_{t-1}\) such that \(x_{v_1}=\max\limits_{z\in V(T)}x_z\) and \(x_{v_{t-1}}=\min\limits_{z\in V(T)}x_z\). By Rayleigh quotient, \[\begin{align} \sigma_1(A(T)-I_{vv}) &=\mathbf{x}^{\top}(A(T)-I_{vv})\mathbf{x} =2\sum_{z\sim w}x_zx_w-x_v^2 \leq 2x_{v_1}\sum_{z\neq v_1}x_z-x_{v_{t-1}}^2 \\ &=\mathbf{x}^{\top}(A({K_{1,t-1}})-I_{v'v'})\mathbf{x} \leq \sigma_1(A({K_{1,t-1}})-I_{v'v'}). \end{align}\] The equality forces \(x_v=x_{v_{t-1}}\) and \(x_w=x_{v_1}\) for every \(w\neq v_1\). Then \(v_1 \sim w\) for every \(w\neq v_1\). Therefore \(T\cong K_{1,t-1}\) and \(v'\) is a leaf of \(K_{1,t-1}\). By Theorem 3 and the claim above, the extremal tree is obtained from two copies of the tree \(K_{1,t-1}\) by joining their leaves, which implies that \(T \cong S^4_{\frac{n-4}{2},\frac{n-4}{2}}\). ◻

Proof. It is clear that outerplanar graphs satisfy the pendant-extension property. By Theorem 2 and Theorem 10, the result follows immediately. ◻

Proof. For \(n \geq 24\), let \((G,v)\) be the pair such that \(\sigma_1(A(G)-I_{v v})\) attains the maximum among all outerplanar graphs of order \(n\) and their vertices. Let \(\sigma = \sigma_1(A(G)-I_{v v})\). Based on 4, let \(\mathbf{x}\) be a positive eigenvector of \(G\) corresponding to \(\sigma\), scaled so that \(x_u=\max_{v\in V(G)} x_v=1\). Let \(A=N_G(u), B=V(G)\setminus (\{u\}\cup A)\), and \(d_G(u)=|A|\). we shall prove that \(B=\emptyset\) and \(G[A]\) is an induced path, which implies that \(G\cong K_1\vee P_{n-1}\).

Let \(L_1=\sqrt n+1-\frac{1}{n-\sqrt n}-\frac{n-\sqrt n}{2n}\) and \(L_2=\sqrt n+1-\frac{3}{2(n-\sqrt n)}\).

Next we recall the structure of \(G[A]\) in [41]. In fact, the proofs of Claims 2, 4 and 5 in [41] depend mainly on the outerplanarity of \(G\) and the fact that \(u\) has the largest eigenvector entry.

Let \(S=\{w\in A:\;d_{G[A]}(w)=1\}.\) We want to show that \(d_G(u)\) is close to \(n-1\). As the first step, we associate \(d_G(u)\) with \(\sigma\) as follows.

We now show that \(|B|\leq 1\). Suppose to the contrary that \(|B|\ge 2\). Let \(B_1,\cdots,B_t\) be the vertex sets of all components of \(G[B]\).

Combining Claims 3 and 5, we obtain, for \(u=v\), \[\begin{align} \left(1-\frac{5}{L_1}\right)d_G(u) &\ge L_1^2-L_1-2+\frac{2}{\sqrt n+1}-\frac{5n-7}{L_1}, \label{eq:minus-y1-du-bound1} \end{align}\tag{15}\] and for \(u \neq v\), \[\begin{align} \left(1-\frac{5}{L_2}\right)d_G(u) &\ge L_2^2-2L_2+\frac{2}{\sqrt n+2}-\frac{5n-7}{L_2}. \label{eq:minus-y1-du-bound2} \end{align}\tag{16}\] We compare the right-hand side with \((n-3)(1-5/L_i)\) for \(i=1,2\).

For \(u = v\), let \(s=\sqrt n\), \(\varepsilon=\frac{s-3}{2s(s-1)}\) and \(L_1=s+1/2+\varepsilon.\) Then, \[\begin{align} &L_1^2-L_1-2+\frac{2}{s+1}-\frac{5s^2-7}{L_1} -(s^2-3)\left(1-\frac{5}{L_1}\right) \\ &= L_1^2-L_1-s^2+1+\frac{2}{s+1}-\frac{8}{L_1} \\ &= \frac{7s-15}{4(s-1)}+\varepsilon^2+\frac{2}{s+1}-\frac{8}{L_1} \\ &> \frac{7s-15}{4(s-1)}+\frac{2}{s+1}-\frac{8}{s+1/2} \\ &= \frac{14s^3-57s^2-46s+41}{4(s-1)(s+1)(2s+1)}. \end{align}\] Let \(q(s)=14s^3-57s^2-46s+41.\) For \(s\ge\sqrt{22}\), we have \(q'(s)=42s^2-114s-46>0\), and \(q(\sqrt{22})=262\sqrt{22}-1213>0\). Therefore \(q(s)>0\) for all \(s \ge \sqrt{22}\), i.e. for all \(n\ge 22\).

For \(u \neq v\), let \(s=\sqrt n\), \(\varepsilon'=\frac{3}{2s(s-1)}\) and \(L_2=s+1-\varepsilon'\), where \(\varepsilon' < \frac{1}{2}\) for \(s>3\). Then \[\begin{align} &L_2^2-2L_2+\frac{2}{s+2}-\frac{5s^2-7}{L_2} -(s^2-3)\left(1-\frac{5}{L_2}\right) \\ &= L_2^2-2L_2-s^2+3+\frac{2}{s+2}-\frac{8}{L_2} \\ &= \frac{2s-5}{s-1}+(\varepsilon')^2+\frac{2}{s+2}-\frac{8}{L_2} \\ &> \frac{2s-5}{s-1}+\frac{2}{s+2}-\frac{8}{s+1/2} \\ &= \frac{4s^3 - 12s^2 - 39s + 20}{(s-1)(s+2)(2s+1)}. \end{align}\] Let \(p(s)=4s^3-12s^2-39s+20.\) For \(s\ge\sqrt{24}\), we have \(p'(s)=12s^2-24s-39>0\), and \(p(\sqrt{24})=57\sqrt{24}-268>0\). Therefore \(p(s)>0\) for all \(s \ge \sqrt{24}\), i.e. for all \(n\ge 24\).

For \(i=1,2\), by (15 ) and (16 ), we have \[\left(1-\frac{5}{L_i}\right)d_G(u)> (n-3)\left(1-\frac{5}{L_i}\right).\] For \(s\geq \sqrt{23}\), we have \(L_2 > L_1 > s+\frac{1}{2}>5\), which implies \(d_G(u)>n-3\). This contradicts \(|B|=n-1-d_G(u)\ge2\). Therefore, we have \(|B|\le 1\). Suppose that \(|B|=1\). At this point, we can know the same information on \(G[A]\) as Claim 6 in [41].

Finally, we show that, indeed, \(B\) is an empty set.

Combining all the claims, it follows that \(G\cong K_1\vee P_{n-1}.\)

Now it suffices to show that \(v\) is either \(v_2\) or \(v_n\). Since \(v_2\) and \(v_n\) are symmetric, \(\sigma_1(M_{v_2}(G))=\sigma_1(M_{v_n}(G))\). It remains to show that every other choice of \(v\) gives a strictly smaller value.

Let \(\mathbf{w}>0\) be a unit eigenvector corresponding to \(\sigma_1(M_v(G))\). We claim that \(w_v\leq w_z\) for \(z\in V(G)\). Indeed, if there exists \(z\neq v\) such that \(w_z<w_v\), then \(M_z(G)=M_v(G)+I_{vv}-I_{zz}\). It follows that \(\sigma_1(M_z(G)) \geq \mathbf{w}^{\top}M_z(G)\mathbf{w} = \mathbf{w}^{\top}M_v(G)\mathbf{w}+w_v^2-w_z^2 > \sigma_1(M_v(G)),\) which contradicts the choice of \(v\).

Assume first that \(v=v_k\) with \(3\leq k\leq n-1\). Then the claim above gives \(w_v\leq w_{v_2}\). Construct a new path on the same vertex set by replacing \(v_2v_3\cdots v_{k-1}v_kv_{k+1}\cdots v_n\) with \(v_k v_{k-1}\cdots v_2 v_{k+1}\cdots v_n\). Equivalently, delete the edge \(v_k v_{k+1}\) and add the edge \(v_2 v_{k+1}\), while keeping \(v_1\) adjacent to all path vertices. Let \(G'\) be the resulting graph and \(M'_v=A({G'})-I_{vv}\). Then \(G'\cong K_1\vee P_{n-1}\), and \(v=v_k\) is an endpoint of the path in \(G'\). Hence \(\sigma_1(M_v(G'))=\sigma_1(M_{v_2}(G))\). Moreover, \(\mathbf{w}^{\top}M_v(G')\mathbf{w}-\mathbf{w}^{\top}M_v(G)\mathbf{w} = 2w_{v_{k+1}}(w_{v_2}-w_v)\geq 0.\) Thus \(\sigma_1(M_{v_2}(G)) = \sigma_1(M_v(G')) \geq \mathbf{w}^{\top}M_v(G')\mathbf{w} \geq \mathbf{w}^{\top}M_v(G)\mathbf{w} = \sigma_1(M_v(G)).\) We claim that the inequality is strict. If the equality holds, then \(\mathbf{w}\) would also be a positive eigenvector of \(M_v(G')\) corresponding to \(\sigma_1(M_v(G'))\). Notice that \(\sigma_1(M_v(G))w_v = w_{v_1}+w_{v_{k-1}}+w_{v_{k+1}}-w_v,\) and \(\sigma_1(M_v(G'))w_v= w_{v_1}+w_{v_{k-1}}-w_v.\) Since \(\sigma_1(M_v(G'))=\sigma_1(M_v(G))\), this gives \(w_{v_{k+1}}=0\), a contradiction. Therefore \(\sigma_1(M_{v_2}(G))>\sigma_1(M_v(G))\), which contradicts the choice of \(v\). Hence no path interior vertex can maximize \(\sigma_1(M_v(G))\).

It remains to exclude \(v=v_1\). Assume that \(v=v_1\), and let \(\mathbf{w}>0\) be a unit eigenvector corresponding to \(\sigma_1(M_{v_1}(G))\). Recall that \(w_{v_1}=w_v \leq w_z\) for \(z\in V(G)\). On the other hand, by the proof of \(G \cong K_1 \vee P_{n-1}\) as above, we have \(w_{v_1}\geq w_z\) for \(z\in V(G)\). Hence \(w_{v_1}=w_z=c>0\) for any \(z\in V(G)\). For \(n\geq 4\), \(N_G(v_2)=\{v_1,v_3\}\), \(N_G(v_3)=\{v_1,v_2,v_4\}.\) The eigen-equation \(M_{v_1}(G)\mathbf{w}=\sigma_1(M_{v_1}(G))\mathbf{w}\) gives \(\sigma_1(M_{v_1}(G))c=2c\) at \(v_2\) and \(\sigma_1(M_{v_1}(G))c= 3c\) at \(v_3\), which is impossible. Therefore \(v\neq v_1\).

The proof is complete. ◻

Proof. It is clear that outerplanar graphs satisfy the pendant-extension property. If \(n\) is even, then by Theorem 3 and Theorem 12, the result follows immediately. ◻

Proof. Let \(A\) be the set of the \(R\) vertices of \(K_r\) adjacent to \(u\), where \(u\) is the new vertex in \(G_m\). Let \(C=V(K_r)\setminus A\). Then \(|A|=R\) and \(|C|=r-R\). By the partition \(A,C,\{u\}\), the adjacency matrix \(A(G_m)\) has the equitable quotient matrix \[\begin{align} Q= \begin{pmatrix} R-1 & r-R & 1\\ R & r-R-1 & 0\\ R & 0 & 0 \end{pmatrix}. \end{align}\] Since \(A(G_m)\) is nonnegative, by Corollary 6, we have \(\rho_1(G_m)=\sigma_1(Q)\). The characteristic polynomial of \(Q\) is \[\begin{align} p(\sigma) =\sigma^3-(r-2)\sigma^2-(r+R-1)\sigma+R(r-R-1). \end{align}\] Then \(p'(\sigma) =3\sigma^2-2(r-2)\sigma-(r+R-1)\), and \(p''(\sigma) = 6\sigma-2(r-2)\). For \(\sigma\geq r-1\), we have \(p''(\sigma)\geq 6(r-1)-2(r-2)=4r-2>0\), which implies that \(p'\) is strictly increasing on \([r-1,\infty)\). Moreover, \(p'(r-1)=r(r-1)-R>0\). It follows that \(p\) is strictly increasing on \([r-1,\infty)\). Let \(a=\frac{R+1}{r+2}\). Then \[\begin{align} p(r-1+a) &=a(r+a)(r-1+a)-R(R+a)=\bigl(a(r+a)-R\bigr)(r-1+a)+R(r-1-R)\\ &=\frac{(r-R+1)^2}{(r+2)^2}(r-1+a)+R(r-1-R)>0. \end{align}\] Since \(p(r-1)=-R^2<0\), \(p\) has exactly one root in \((r-1,\infty)\), especially in \((r-1,r-1+\frac{R+1}{r+2})\), which implies that \(\sigma_1(Q)<r-1+\frac{R+1}{r+2}\). This proves the lemma. ◻

Proof. We first prove the upper bound under the first condition. Fix a maximum clique \(K_{\omega}\) of order \(\omega\). Let \(S=V(G)\setminus V(K_\omega)\) and \(s=|S|\). Let \(e(G)=\binom{\omega}{2}+R\). Then \(1\leq R\leq \omega\). Since \(G\) is connected, \(s\leq R\). If \(s\geq 3\), then \(n=\omega+s\) and \(m=\binom{\omega}{2}+R\). By Theorem 15, we have \[\begin{align} \rho_1(G)^2 \leq 2m-n+1 =(\omega-1)^2+2R-s . \end{align}\] Let \(t=\omega-1+\frac{R}{\omega+1}\), as \(s\geq 3\) and \(R\leq \omega\), then \[\begin{align} t^2-\bigl((\omega-1)^2+2R-s\bigr) =s-\frac{4R}{\omega+1}+\frac{R^2}{(\omega+1)^2} \geq (s-4)+\left(\frac{\omega+2}{\omega+1}\right)^2>0. \end{align}\] Thus \(\rho_1(G)<t\) in this case.

It remains to consider \(s=1\) and \(s=2\). Write the adjacency matrix of \(G\) as \[\begin{align} A(G)= \begin{pmatrix} J_\omega-I_\omega & M\\ M^{\top} & C \end{pmatrix}, \end{align}\] where \(J_\omega\) is the all-one matrix and \(C=A(G[S])\). Since \(t>\omega-1\), the matrix \(P\mathrel{\vcenter{:}}= tI_\omega-(J_\omega-I_\omega)\) is positive definite, and then \(P^{-1} = \alpha I_\omega+\beta J_\omega\) where \(\alpha=\frac{1}{t+1}\) and \(\beta=\frac{1}{(t+1)(t-\omega+1)}\). Since \(A(G)\) is symmetric, \(\rho_1(G)\leq t\) is equivalent to showing that \(tI-A(G)\) is positive semi-definite, where \[\begin{align} tI-A(G)= \begin{pmatrix} tI_\omega-(J_\omega-I_\omega) & -M\\ -M^{\top} & tI_s-C \end{pmatrix}. \end{align}\] Therefore, by the Schur complement, \(tI-A(G)\geq 0\) is equivalent to \(tI_s-C-M^{\top}P^{-1}M\geq 0\). Since \(C+M^{\top}P^{-1}M\) is symmetric, it remains to prove \(\sigma_1\bigl(C+M^{\top}P^{-1}M\bigr)< t\).

For \(s=1\), the unique vertex of \(S\) is adjacent to exactly \(R\) vertices of \(K\). Since \(\omega(G)=\omega\) and \(G\not\cong K_{\omega+1}-e\), we have \(R\leq \omega-2\). Thus \(C+M^{\top}(\alpha I_\omega+\beta J_\omega)M = \alpha R+\beta R^2\). A direct calculation gives \[\begin{align} t-\alpha R-\beta R^2 = \frac{ R^2-R(\omega^3+2\omega^2+4\omega+3) +\omega^4+\omega^3-\omega^2-\omega }{ (\omega+1)(R+\omega^2+\omega) }. \end{align}\] The numerator is decreasing in \(R\) for \(1\leq R\leq \omega-2\), and at \(R=\omega-2\) it equals \(\omega^3+10>0\). Hence \(\rho_1(G)< t\).

For \(s=2\), we denote \(S=\{x,y\}\). Let \(a=|N_G(x)\cap K|\) and \(b=|N_G(y)\cap K|\).

If \(xy\notin E(G)\), then \(a+b=R\), and \(a,b\geq 1\) by connectedness. The matrix \(M^{\top}(\alpha I_\omega+\beta J_\omega)M\) is positive semi-definite, so its largest eigenvalue is at most its trace. Hence \[\begin{align} \sigma_1\bigl(M^{\top}(\alpha I_\omega+\beta J_\omega)M\bigr) \leq \alpha(a+b)+\beta(a^2+b^2)\leq \alpha R+\beta\bigl((R-1)^2+1\bigr). \end{align}\] We now show that \(\alpha R+\beta\bigl((R-1)^2+1\bigr)< t\). Let \(D=R+\omega^2+\omega\), and we have \(\alpha=\frac{1}{t+1} =\frac{\omega+1}{D}\), \(\beta = \frac{(\omega+1)^2}{RD}.\) Thus \[\begin{align} t-\alpha R-\beta\bigl((R-1)^2+1\bigr)= \frac{F(R)}{R(\omega+1)D}, \end{align}\] where \(F(R)= R^3 -R^2(\omega^3+2\omega^2+4\omega+3) +R(\omega^4+3\omega^3+5\omega^2+5\omega+2) -2(\omega+1)^3\). It follows that \[\begin{align} F''(R) = 6R-2(\omega^3+2\omega^2+4\omega+3) \leq -2\omega^3-4\omega^2-2\omega-6 <0. \end{align}\] Hence \(F(R)\) is concave on \([2,\omega]\). Therefore we only need to check \(F(2)\) and \(F(\omega)\). We have \(F(2)=2(\omega^4-2\omega^2-6\omega-1)>0\) and \(F(\omega)=\omega^4-4\omega^2-4\omega-2>0\) for every \(\omega\geq 3\). It follows that \(F>0\) for \(2\leq R\leq \omega\). Consequently, \(\alpha R+\beta\bigl((R-1)^2+1\bigr)<t\).

If \(xy\in E(G)\), then \(a+b=R-1\). If \(a,b\geq 1\), by Lemma 5 and the similar calculation as above, \[\begin{align} \sigma_1\bigl(C+M^{\top}(\alpha I_\omega+\beta J_\omega)M\bigr) &\leq 1+\operatorname{tr}\bigl(M^{\top}(\alpha I_\omega+\beta J_\omega)M\bigr)\\ &\leq 1+\alpha(R-1)+\beta\bigl((R-2)^2+1\bigr) < t. \end{align}\] If one of \(a,b\) is zero, WLOG let \(b=0\), then \(a=R-1\), and \[\begin{align} C+M^{\top}(\alpha I_\omega+\beta J_\omega)M = \begin{pmatrix} u & 1\\ 1 & 0 \end{pmatrix}, \quad u=\alpha(R-1)+\beta(R-1)^2. \end{align}\] By direct calculation, \(\rho_1(G)< t\).

It remains to prove the upper bound under the second condition. If \(m\leq \binom{\omega}{2}-1\), then \(m=\binom r2+R\) with \(0\leq R\leq r-1\), where \(r\leq \omega-1\). For \(0< R\leq r-1\), by Theorem 16 and Lemma 12, we have \[\rho_1(G)\leq \rho_1(G_m)< r-1+\frac{R+1}{r+2}=\frac{\binom{r+2}{2}+m-2}{r+2}.\] For \(R=0\), by Theorem 15, \(\rho_1(G)\leq \sqrt{2\binom{r}{2}-r+1}=r-1<r-1+\frac{1}{r+2}\). It follows that \(\rho_1(G)<\frac{\binom{r+2}{2}+m-2}{r+2}\) holds for all \(0\leq R\leq r-1\). Define \(\phi(x)=\frac{\binom{x}{2}+m-2}{x}\). Since \(m\leq \binom{r}{2}+r-1\), we have \(\phi'(x)>0\) for \(x\geq r+2\). Since \(r+2\leq \omega+1\), then \(\frac{\binom{r+2}{2}+m-2}{r+2}<\frac{\binom{\omega+1}{2}+m-2}{\omega+1}=\omega-1+\frac{m-\binom{\omega}{2}-1}{\omega+1}\). Therefore, we have \(\rho_1(G)<\omega-1+\frac{m-\binom{\omega}{2}-1}{\omega+1}\).

If \(m=\binom{\omega}{2}\), then \(\omega-1+\frac{m-\binom{\omega}{2}-1}{\omega+1}=\omega-1-\frac{1}{\omega+1}\). It is clear that \(\omega(G)\leq \omega-1\) because \(G\not\cong K_{\omega}\). For \(\omega=3\), \(G\) is a tree with \(m=3\). Since the star uniquely attains the maximum spectral radius among all graphs of a given order [39], we have \(\rho_1(G)\leq\rho_1(K_{1,3})=\sqrt3<\frac{7}{4}=\omega-1-\frac{1}{\omega+1}\). For \(\omega\geq 4\), if \(\omega(G)\leq \omega-2\), we have \(\rho_1(G)^2\leq 2\binom{\omega}{2}\left(1-\frac{1}{\omega-2}\right)=\omega(\omega-1)\frac{\omega-3}{\omega-2}<\left(\omega-1-\frac{1}{\omega+1}\right)^2\) by Theorem 14. It remains to consider that \(\omega(G)=\omega-1\). Since \(m=\binom{\omega}{2}\), then \(G\not\cong K_\omega-e\). By the first upper bound, we have \(\rho_1(G)< \omega-2+\frac{\omega-1}{\omega}=\omega-1-\frac{1}{\omega}<\omega-1-\frac{1}{\omega+1}\). The proof is complete. ◻

Proof. For \(\omega=2\), \(K_2O_1K_1\cong K_2\). Clearly, \(\rho_2(K_2)=-1<-\frac{1}{2}=\frac{m-2}{\omega}\). Assume that \(\omega\geq 3\). Since \(m=\binom{\omega}{2}+\binom{\omega-1}{2} =(\omega-1)^2\), we have \(\frac{m-2}{\omega} = \frac{(\omega-1)^2-2}{\omega} =\omega-2-\frac{1}{\omega}\). The characteristic polynomial \(P(K_{n_1}O_kK_{n_2};x)\) of \(k\)-coalescence \(K_{n_1}O_kK_{n_2}\) is given by \[\begin{align} P(K_{n_1}O_kK_{n_2};x) &= (x+1)^{n_1+n_2-k-3} \Big[x^3-(n_1+n_2-k-3)x^2 \\ &+ \big((n_1-k-1)(n_2-k-1) +(k-1)(n_1+n_2-2k-2) \\ &- k(n_1+n_2-2k)\big)x + k(n_1-k)(n_2-k-1)\\ &+k(n_2-k)(n_1-k-1) -(k-1)(n_1-k-1)(n_2-k-1) \Big]; \end{align}\] see [47]. Then \[\begin{align} P(K_{\omega}O_1K_{\omega-1};x)= (x+1)^{2\omega-5} \Big( x^3-(2\omega-5)x^2 + (\omega^2-7\omega+9)x +2\omega^2-8\omega+7 \Big). \end{align}\] Let \(f(x)= x^3-(2\omega-5)x^2 +(\omega^2-7\omega+9)x +2\omega^2-8\omega+7\). Denote three roots of \(f\) by \(\alpha_1\geq \alpha_2 \geq \alpha_3\). Since \(f(-2)=1-2\omega<0\), \(f(-1)=(\omega-2)(\omega-1)>0\), \(f(\omega-3)=\omega-2>0\), \(f\left(\omega-2-\frac{1}{\omega}\right) = -\frac{\omega^4-2\omega^3+\omega+1}{\omega^3}<0\), \(f(\omega-1)=2-\omega<0\), and \(f(\omega)=\omega+7>0\), we have \[\begin{align} \alpha_1\in(\omega-1,\omega), \qquad \alpha_2\in \left(\omega-3,\;\omega-2-\frac{1}{\omega}\right), \qquad \alpha_3\in(-2,-1). \end{align}\] All the remaining \(2\omega-5\) eigenvalues of \(K_{\omega}O_1K_{\omega-1}\) are \(-1\). Since \(\omega\geq 3\), we have \(\alpha_2>\omega-3\geq 0>-1\). Then \(\rho_2(K_\omega O_1K_{\omega-1})=\alpha_2\). Therefore \[\begin{align} \rho_2(K_\omega O_1K_{\omega-1}) = \alpha_2 < \omega-2-\frac{1}{\omega}=\frac{m-2}{\omega}. \end{align}\] This completes the proof. ◻

Proof. We first consider that \(c=0\). For \(c=0\), we have \(a+b=\omega\) and \(r=ab\). Let \(A(x)=x-ab\) and \(B(x)=2\left(x-\binom{\omega}{2}+\binom b2\right)\). Moreover, \(b\geq 2\) and \(a\leq \omega-2\). Clearly, \[\begin{align} \min\{A(x),B(x)\}= \begin{cases} B(x), & x\leq M,\\ A(x), & x\geq M, \end{cases} \end{align}\] where \(M=a(\omega-1)\) and \(A(M)=B(M)\). Let \(F(x) = \frac{(x-2)^2}{\omega^2}-\frac{\omega-3}{\omega-2}\min\{A(x),B(x)\}.\) For \(x\leq M\), \(F'(x)=\frac{2(x-2)}{\omega^2} -\frac{2(\omega-3)}{\omega-2} \leq \frac{2(a(\omega-1)-2)}{\omega^2} -\frac{2(\omega-3)}{\omega-2} \leq \frac{2((\omega-1)(\omega-2)-2)}{\omega^2} -\frac{2(\omega-3)}{\omega-2} <0.\) It follows that \(F(x)\geq F(M)=\frac{(b-2)P(a,b)}{\omega^2(\omega-2)}\), where \(P(a,b)=a^3+(2b-5)a^2+(b^2-5b+2)a+4.\) Then \(\frac{\partial P}{\partial a}= 3a^2+2(2b-5)a+(b^2-5b+2)\geq 8b^2-15b+2>0\) due to \(a\geq b\), which implies that \(P(a,b)\geq P(b,b)=2(b-2)(b-1)(2b+1)\geq 0.\) Therefore, we have \(F(x) \geq F(M)\geq 0\) for \(x\leq M\).

For \(x\geq M\), \(F'(x)=\frac{2(x-2)}{\omega^2} -\frac{\omega-3}{\omega-2}.\) Solving \(F'(x)=0\) gives \(x_0=2+\frac{\omega^2(\omega-3)}{2(\omega-2)}.\) If \(x_0\leq M\), then \(F\) is increasing on \([M,\infty)\), and \(F(x)\geq F(M)\geq 0\).

Suppose that \(x_0>M\). Since \(F\) is convex on \([M,\infty)\), \(F\) attains its minimum at \(x_0\). By calculation, the inequality \(x_0>M\) is equivalent to \(a<\frac{\omega^3-3\omega^2+4\omega-8}{2(\omega-1)(\omega-2)}.\) Note that \(F(x_0)=\frac{\omega-3}{\omega-2} \left(ab-2-\frac{\omega^2(\omega-3)}{4(\omega-2)} \right).\) It suffices to prove \(ab-2-\frac{\omega^2(\omega-3)}{4(\omega-2)}>0.\) Let \(A=\frac{\omega^3-3\omega^2+4\omega-8}{2(\omega-1)(\omega-2)}.\) Since \(a\geq b\), we have \(a\geq \omega/2\). Moreover, the function \(g(y)=y(\omega-y)\) is decreasing on \([\omega/2,\infty)\). Then \[ab=a(\omega-a)>A(\omega-A)= 2+\frac{\omega^2(\omega-3)}{4(\omega-2)}+ \frac{(\omega-4)^2(\omega-3)(\omega^2-\omega+2)}{4(\omega-2)^2(\omega-1)^2}.\] So \(ab>2+\frac{\omega^2(\omega-3)}{4(\omega-2)}.\) Consequently, \(F(x)\geq F(x_0)>0\) for all \(x\geq M\).

Taking \(x=m\), we obtain the desired inequality for \(c=0\).

Next we consider that \(c>0\). Suppose that \(b\geq 2\). We prove that \(L(a,b,c)\leq L(a+c,b,0)\). Note that \(r-\bigl((a+c)b\bigr)=ab+c(a+b)+\binom c2-(a+c)b=ac+\binom c2> 0.\) Then \(m-r < m-(a+c)b\). Since \(b\) is unchanged, the second term in \(L(a,b,c)\) is unchanged. Therefore \(L(a,b,c)\leq L(a+c,b,0)\).

If \(b=1\), then \(c\geq1\) and \(a+c=\omega-1\). We compare \(L(a,1,c)\) with \(L(\omega-2,2,0)\). Note that \(r-2(\omega-2)= a(c-1)+\frac{c^2-3c+4}{2} >0\), and we have \(m-r<m-2(\omega-2)\). Besides, \(x-\binom{\omega}{2} <x-\binom{\omega}{2}+\binom 22\). Consequently, \(L(a,1,c)< L(\omega-2,2,0)\), which implies that 17 is strict. If \(b=0\), then \(c\geq2\) and \(a+c=\omega\). Again we compare \(L(a,0,c)\) with \(L(\omega-2,2,0)\). Since \(r-2(\omega-2)= 1+\frac{(c-2)(2\omega-c-3)}{2} >0\), we have \(m-r<m-2(\omega-2)\). Besides, \(x-\binom{\omega}{2} <x-\binom{\omega}{2}+\binom 22\). Then \(L(a,0,c)< L(\omega-2,2,0)\), which implies that 17 is strict.

The proof is complete. ◻

Proof of Theorem 5. Let \(G\) be a connected graph of order \(n\geq 2\), size \(m\), and clique number \(\omega\). Clearly, \(\omega\geq 2\). If \(n=2\), then \(G\cong K_2\), so the assertion is immediate. Assume that \(n\geq 4\). If \(\rho_2(G)=0\), then \(|\rho_2(G)|\omega=0\), and there is nothing to prove. If \(\rho_2(G)<0\), then \(G\) is a complete graph. In this case \(\omega=n\), \(m=\binom n2\), and \(|\rho_2(G)|=1\). If \(n\) is odd, then \(|\rho_2(G)|\omega=n \leq \binom n2-2=m-2\), where the inequality strictly holds for odd order \(n\geq 5\). If \(n\) is even, then we claim that \(|\rho_2(G)|\omega-e(G) \leq -2< |\rho_2(2K_\omega+e)|\omega-e(2K_\omega+e))\). The characteristic polynomial \(P(2K_\omega+e;x)\) of \(2K_\omega+e\) is given by \(P(2K_\omega+e;x) =(x+1)^{2\omega-4} \left(x^2-(\omega-1)x-1\right) \left(x^2-(\omega-3)x-(2\omega-3)\right)\). Then \(\rho_2(2K_\omega+e)= \frac{\omega-3+\sqrt{(\omega-1)(\omega+3)}}{2}\). For \(\omega\geq 2\), we have \(\omega\rho_2(2K_\omega+e)-e(2K_\omega+e)= \frac{\omega(\omega-3)+\omega\sqrt{(\omega-1)(\omega+3)}}{2}-\omega(\omega-1)-1= \frac{ \omega\sqrt{(\omega-1)(\omega+3)} -\omega^2-\omega-2 }{2}>-2.\) Consequently, \(|\rho_2(G)|\omega-e(G) \leq -2< |\rho_2(2K_\omega+e)|\omega-e(2K_\omega+e)\). Therefore, in the rest of the proof, we may assume that \(\rho_2>0\).

Let \(f\) be a \(\rho_2\)-eigenfunction, and let \(U_1,\ldots,U_l\) be the nodal domains of \(f\). Write \(\Omega_{U_i}\) as \(\Omega_i\) for simplicity. Let \(G[\Omega_i]\) be the subgraph of \(G\) induced by \(\Omega_i\). Let \(\kappa = \max_{1\leq i\leq l}\omega(G[\Omega_i])\). Clearly, \(\kappa\leq \omega\). Denote \(m_i=e(G[\Omega_i])\). Let \(r=m-\sum_{i=1}^l m_i\). By Theorem 9 and Corollary 1, for each nodal domain \(U_i\), \[\begin{align} \label{eq:nodal95basic95comparison} \rho_2=\mu_1(G_{U_i})\leq \rho_1(G[\Omega_i]). \end{align}\tag{18}\] If there exists a boundary edge with positive weight in \(G_{U_i}\), then the inequality of 18 is strict.

We first give the following inequality. If \(m_i+r \geq \binom{\omega}{2}+2\), then there exists \(j\neq i\) such that \[\begin{align}\label{eq951951951} 2m_j\frac{\omega-1}{\omega} \leq 2\left(m-\binom{\omega}{2}-2\right)\frac{\omega-1}{\omega} \leq \frac{(m-2)^2}{\omega^2}, \end{align}\tag{19}\] where the equality in 19 holds if and only if \(m=\omega^2-\omega+2\) and \(m_j=m-\binom{\omega}{2}-2=\binom{\omega}{2}\).

Let \(Z\mathrel{\vcenter{:}}= V(G)\setminus \bigcup_{k=1}^l \Omega_k =\{u\in V(G):f(u)=0\}\). We divide the argument into two cases based on whether \(Z\) is empty.

Case . \(Z\neq\emptyset\).

We distinguish the following three subcases according to the value of \(\kappa\).

Subcase .. \(\kappa=\omega\).

Choose a nodal domain \(U\) such that \(G[\Omega_U]\) contains a clique \(K_\omega\). WLOG, we may assume that \(U=U_1\). Since \(Z\neq\emptyset\), at least two edges of \(G\) are not internal to any nodal domain. It follows that \(r\geq 2\). Then \(m_1+r \geq \binom{\omega}{2}+2\). By 19 , there exists another nodal domain \(U_j\) such that \(2m_j\frac{\omega-1}{\omega} \leq \frac{(m-2)^2}{\omega^2}\). Thus, by 18 and Theorem 14, we have \[\begin{align}\label{eq95Z95a951} \rho_2^2 \leq \rho_1^2(G[\Omega_j])\leq 2m_j\frac{\omega-1}{\omega} \leq \frac{(m-2)^2}{\omega^2}. \end{align}\tag{20}\]

Subcase .. \(\kappa=\omega-1\).

If \(\omega=2\), then \(\kappa =1\). Hence every \(G[\Omega_i]\) is a single vertex. By 18 , we have \(\rho_2\leq0\), contrary to our assumption \(\rho_2>0\). Therefore, we may assume that \(\omega\geq3\).

Choose a nodal domain \(U\) such that \(G[\Omega_U]\) contains a clique \(K_{\omega-1}\). WLOG, we may assume that \(U=U_1\). Then \(m_1\geq \binom{\omega-1}{2}.\) Since no nodal domain contains \(K_\omega\), the clique \(K_\omega\) in \(G\) contributes at least \(\omega-1\) edges that are not internal to any nodal domain. Moreover, since \(Z\neq\emptyset\) and \(f\) has both positive and negative entries, there is at least one more edge which is not internal to any nodal domain. Hence \(r\geq \omega\). Let \(U_2\) be another nodal domain different from \(U_1\). It follows that \(m_2 \leq m-\binom{\omega-1}{2}-\omega\) due to \(\min\{2m_1,2m_2\}\leq m_1+m_2\leq m-\omega\). By 18 and Theorem 14, \[\begin{align}\label{eq95Z95a952} \rho_2^2 \leq \min\{\rho_1^2(G[\Omega_1]), \rho_1^2(G[\Omega_2])\} \leq \min\{m-\omega, 2(m-\binom{\omega-1}{2}-\omega)\}\frac{\omega-2}{\omega-1}. \end{align}\tag{21}\] We claim that \(\rho_2^2\le \frac{(m-2)^2}{\omega^2}.\) Let \(A(x)=(x-\omega)\) and \(B(x)= 2(x-\binom{\omega-1}{2}-\omega).\) It suffices to show that \(\min\{A(m),B(m)\}\frac{\omega-2}{\omega-1}\leq \frac{(m-2)^2}{\omega^2}\). Clearly, \[\begin{align} \min\{A(x),B(x)\}= \begin{cases} B(x), & x\leq M,\\ A(x), & x\geq M, \end{cases} \end{align}\] where \(M=\omega^2-2\omega+2\) and \(A(M)=B(M)\). Let \(F(x)= \frac{(x-2)^2}{\omega^2}-\min\{A(x),B(x)\}\frac{\omega-2}{\omega-1}\). For \(x\leq M\), \(F'(x) = \frac{2(x-2)}{\omega^2}- 2\frac{\omega-2}{\omega-1}< 0\), which implies that \(F(x)\geq F(M)=0\). For \(x\geq M\), \(F'(x) = \frac{2(x-2)}{\omega^2} - \frac{\omega-2}{\omega-1} \geq 0\), which implies that \(F(x)\geq F(M)=0\). Therefore, we have \(\rho_2^2\le \frac{(m-2)^2}{\omega^2}\).

Subcase .. \(\kappa \leq \omega-2\).

Since \(\kappa\geq1\), \(\omega\geq 3\). If \(\omega=3\), then \(\kappa=1\). Hence each \(G[\Omega_i]\) is a single vertex. By 18 , we have \(\rho_2\leq0\). Assume that \(\omega\geq4\).

Choose a maximum clique \(K_\omega\) of \(G\). Let \(U\) be a nodal domain such that \(|K_\omega\cap \Omega|=\max_i |K_\omega\cap \Omega_i|\), where \(\Omega\) is the interior of \(U\). WLOG, assume that \(U=U_1\). Let \(a=|K_\omega\cap \Omega_1|\). Replacing \(f\) by \(-f\) if necessary, assume that \(U_1\) is a positive nodal domain. Note that \(K_\omega\) can merely intersect with one positive nodal domain. If a negative nodal domain intersects \(K_\omega\), let \(U_2\) be that domain; otherwise, choose an arbitrary negative nodal domain and still denote it by \(U_2\). Let \(b=|K_\omega\cap \Omega_2|\) and \(c=|K_\omega\cap Z|\). Then \(a+b+c=\omega\) and \(a\geq b\geq0\). Since \(\kappa\leq\omega-2\), we have \(a\leq\omega-2\). Then \(b+c\geq2\). Let \[\begin{align} \label{eq:clique95crossing95r} r_K=ab+c(a+b)+\binom c2, \end{align}\tag{22}\] where \(r_K\) counts the edges of \(K_\omega\) which are not contained in any nodal domain. It follows that \(r\geq r_K\). So \(\min\{2m_1,2m_2\}\leq m_1+m_2 \leq m-r\leq m-r_K\), and \(m_1+r_K\geq \binom{\omega}{2}-\binom b2\). Then by 18 , 22 , Theorem 14, and Lemma 15, we have \[\begin{align} \rho_2^2 \leq \min\{2m_1,2m_2\}\frac{\omega-3}{\omega-2} \leq \min\left\{m-r_K,\,2\left(m-\binom{\omega}{2}+\binom b2\right)\right\} \frac{\omega-3}{\omega-2}\leq \frac{(m-2)^2}{\omega^2}. \end{align}\] If \(b\neq 0\), then \(K_\omega\) intersects both positive and negative nodal domains, which implies that the total boundary edge weights in \(G_U\) do not vanish. Therefore the inequalities in 18 are strict for \(i=1,2\). If \(b=0\), then the inequality in the Lemma 15 is strict. Therefore, the equality cannot hold in this subcase.

Case . \(Z=\emptyset\).

Since \(Z=\emptyset\), by Theorem 2 in  [28], the eigenfunction \(f\) corresponding to \(\rho_2(G)\) has exactly two nodal domains, denoted by \(U_1\) and \(U_2\). Moreover, for each \(i=1,2\), every boundary edge weight in \(G_{U_i}\) is nonzero. Thus the inequality 18 is strict.

We distinguish the following three subcases.

Subcase .. \(\kappa = \omega\).

We may assume that \(G[\Omega_1]\) contains a clique \(K_\omega\), and we have \(m_1\geq \binom{\omega}{2}\). If \(m_1+r\geq \binom{\omega}{2}+2\), then for the nodal domain \(U_2\), by 18 ,  19 , and Theorem 14, we have \(\rho_2^2 < \rho_1^2(G[\Omega_2])\leq 2m_2\frac{\omega-1}{\omega} \leq \frac{(m-2)^2}{\omega^2}.\)

It remains to consider \(m_1+r=\binom{\omega}{2}+1\). Since \(m_1\geq\binom{\omega}{2}\) and \(r\geq1\), this forces \(m_1=\binom{\omega}{2}\) and \(r=1\). Then \(G[\Omega_1]\cong K_\omega\). Since the inequality 18 is strict, it gives \(\rho_2<\rho_1(K_\omega)=\omega-1\). By 18 and Lemma 6, we have \(\rho_2 = \sigma_1(A(K_\omega)-I_{vv})\geq\sigma_1(A(K_{\omega-1}))=\omega-2\). Thus \(\rho_2 \in [\omega-2, \omega-1)\). Next, we divide the size of \(m_2\) into three cases.

Firstly, \(m_2\geq \binom{\omega}{2}+1\). It follows that \(m=m_1+m_2+r\geq \omega(\omega-1)+2\). Hence \(\rho_2<\omega-1 \leq \frac{m-2}{\omega}\).

Secondly, \(m_2\leq \binom{\omega-1}{2}\). If \(G[\Omega_2]\not\cong K_{\omega-1}\), then, by Lemma 13 and 18 , we have \(\rho_2<\omega-2-\frac{1}{\omega}\), a contradiction with \(\rho_2\geq\omega-2\). If \(G[\Omega_2]\cong K_{\omega-1}\), then, by 18 , we have \(\rho_2<\rho_1(K_{\omega-1})=\omega-2\), a contradiction.

Finally, we assume that \(m_2=\binom{\omega-1}{2}+R,\) where \(1\leq R\leq \omega-1.\) For \(\omega(G[\Omega_2])\leq \omega-2\), by 18 and Theorem 14, we have \[\rho_2^2< 2\left(\binom{\omega-1}{2}+R\right)\frac{\omega-3}{\omega-2}< \left(\omega-2+\frac{R}{\omega}\right)^2= \left(\frac{m-2}{\omega}\right)^2.\]

For \(\omega(G[\Omega_2])=\omega-1\), we claim that \(\omega\geq3\). If \(\omega=2\), then \(G[\Omega_2]\) is a single vertex. By 18 , we have \(\rho_2\leq0\), contrary to our assumption \(\rho_2>0\). If \(G[\Omega_2] \not\cong K_{\omega}-e\), then by 18 and Lemma 13, we have \(\rho_2<\rho_1(G[\Omega_2]) \leq \omega-2+\frac{R}{\omega}=\frac{m-2}{\omega}\). It remains to consider the exceptional case \(G[\Omega_2]\cong K_{\omega}-e\), which implies that \(|\Omega_2|=\omega\). The graph \(G\) now satisfies \(G[\Omega_1]\cong K_\omega\), \(G[\Omega_2]\cong K_\omega-e\), and \(r=1\), where \(G\) is of even order. Let \(u\in V(K_\omega)\). Let \(v_1v_2\) be the missing edge of \(K_\omega-e\). Define \(G_1\mathrel{\vcenter{:}}= (K_\omega-e)\cup K_\omega+uv_1\). For some \(v'\in V((K_\omega-e))\setminus\{v_1,v_2\}\), define \(G_2\mathrel{\vcenter{:}}= (K_\omega-e)\cup K_\omega+uv'\). Let \(q_\omega(x)=x^2-(\omega-3)x-2(\omega-2)\), \(f_1(x)=x(x-\omega+1)q_\omega(x)-(x-\omega+2)^2\), and \(f_2(x)= (x+1)^2(x-\omega+1)q_\omega(x) -(x-\omega+2)q_{\omega-1}(x).\) The characteristic polynomial \(P(G_1;x)\) and \(P(G_2;x)\) are given by \[\begin{align} P(G_1;x)= (x+1)^{2\omega-4}f_1(x),\quad P(G_2;x)=x(x+1)^{2\omega-6}f_2(x). \end{align}\] For each \(i=1,2\), we claim that the polynomial \(f_i(x)\) has exactly one root in \((\omega-2,\omega-1)\) and this root is precisely \(\rho_2(G_i)\). Note that \(f_1(\omega-2)f_1(\omega-1)=-(\omega-2)^2<0\) and \(f_2(\omega-2)f_2(\omega-1)=-(\omega-1)^2(\omega-2)(\omega+3)<0\), which implies that \(f_i(x)\) has some roots in \((\omega-2,\omega-1)\). Since \(G_i\) is obtained from \((K_\omega-e)\cup K_\omega\) by adding one edge, by Lemma 5, \(\rho_3(G_i)\leq \rho_3((K_\omega-e)\cup K_\omega))+1\leq \omega-2\). On the other hand, since \(G_i\) is connected and properly contains \(K_\omega\), by Lemma 9, we have \(\rho_1(G_i)>\omega-1\). Therefore, \(f_i(x)\) has exactly one root in \((\omega-2,\omega-1)\), and this root is precisely \(\rho_2(G_i)\). Let \(\alpha=\rho_2(G_1)\). Then \(f_1(\alpha)=0\), and \(\alpha(\alpha-\omega+1)q_\omega(\alpha)=(\alpha-\omega+2)^2\). Using this equality, we obtain that \[\begin{align} f_2(\alpha) &=(\alpha+1)^2(\alpha-\omega+1)q_\omega(\alpha) -(\alpha-\omega+2)q_{\omega-1}(\alpha)\\ &=\frac{(\alpha+1)^2}{\alpha}(\alpha-\omega+2)^2 -(\alpha-\omega+2)q_{\omega-1}(\alpha)\\ &=(\alpha-\omega+2) \left( \frac{(\alpha+1)^2(\alpha-\omega+2)}{\alpha} -q_{\omega-1}(\alpha) \right)\\ &=-\frac{(\alpha-\omega+2)(\alpha+\omega-2)}{\alpha}<0. \end{align}\] Note that \(f_2(\omega-2)>0\). Thus \(f_2\) has a root in \((\omega-2,\alpha)\), which implies that \(\rho_2(G_2)<\alpha=\rho_2(G_1)\). Then \(\omega\rho_2(G_2)-e(G_2) < \omega\rho_2(G_1)-e(G_1)\).

For \(\omega(G[\Omega_2])=\omega\), \(m_2=\binom{\omega}{2}\). Then \(G\) consists of two copies of \(K_{\omega}\) joined by an edge; that is, \(G\cong 2K_{\omega}+e\). Now we show that \(\omega\rho_2(G_1)-e(G_1) < \omega\rho_2(2K_{\omega}+e)-e(2K_{\omega}+e)\). Recall that \(\rho_2(2K_\omega+e)=\frac{\omega-3+\sqrt{(\omega-1)(\omega+3)}}{2}\). Note that \(f_1(\omega-1-\frac{2}{\omega}+\frac{1}{2\omega^2})<0\). Therefore, we have \[\begin{align} \rho_2(G_1)<\omega-1-\frac{2}{\omega}+\frac{1}{2\omega^2}<\frac{\omega-3+\sqrt{(\omega-1)(\omega+3)}}{2}-\frac{1}{\omega}=\rho_2(2K_{\omega}+e)-\frac{1}{\omega}. \end{align}\] It follows that \[\omega\rho_2(G_1)-e(G_1)< \omega\left(\rho_2(2K_{\omega}+e)-\frac{1}{\omega}\right)-e(G_1) =\omega\rho_2(2K_{\omega}+e)-e(2K_{\omega}+e).\] Moreover, recall that \(\omega\rho_2(2K_\omega+e)-e(2K_\omega+e) >-2\). Overall, we have \(\rho_2(G)\omega-e(G)<-2\) for odd order, and the graph \(2K_\omega+e\) attains the maximum value of \(\rho_2(G)\omega-e(G)\) for even order.

Subcase .. \(\kappa = \omega-1\).

If \(\omega=2\), then \(\kappa=1\). So every \(G[\Omega_i]\) is a single vertex. By 18 , we have \(\rho_2\leq0\), contrary to our assumption \(\rho_2>0\). Therefore, we may assume that \(\omega\geq3\).

Assume that \(G[\Omega_1]\) contains \(K_{\omega-1}\). Then \(m_1\geq \binom{\omega-1}{2}\). Since no nodal domain contains \(K_\omega\), every maximum clique \(K_\omega\) with both \(G[\Omega_1]\) and \(G[\Omega_2]\). Therefore, such a clique contributes at least \(\omega-1\) edges between \(G[\Omega_1]\) and \(G[\Omega_2]\), which implies that \(r\geq \omega-1\). Then, \(m_1+r\geq \binom{\omega-1}{2}+\omega-1=\binom{\omega}{2}\). If \(m_1+r\geq \binom{\omega}{2}+2\), by 18 , 19 , and Theorem 14, we have \(\rho_2^2 < \frac{(m-2)^2}{\omega^2}\).

It remains to consider that \(m_1+r=\binom{\omega}{2}+\delta\) with \(\delta\in\{0,1\}\). Suppose first that \(m_2\leq \binom{\omega-1}{2}\). If \(G[\Omega_2]\not\cong K_{\omega-1}\), then, by 18 and Lemma 13, we have \[\begin{align} \rho_2< \rho_1(G[\Omega_2]) <\omega-2+ \frac{m_2-\binom{\omega-1}{2}-1}{\omega} \leq \frac{m-2}{\omega}. \end{align}\] If \(G[\Omega_2]\cong K_{\omega-1}\) and \(\delta=1\), then by 18 , we have \(\rho_2<\rho_1(G[\Omega_2])=\omega-2=\frac{m-2}{\omega}\). If \(G[\Omega_2]\cong K_{\omega-1}\) and \(\delta=0\), then \(m_1=\binom{\omega-1}{2}\) and \(r=\omega-1\). Hence \(G[\Omega_1]\cong K_{\omega-1}\), and the equality \(r=\omega-1\) forces \(G\cong K_\omega O_1K_{\omega-1}\). By 14, we have \(\rho_2(K_\omega O_1K_{\omega-1})< \frac{m-2}{\omega}\).

Now suppose that \(m_2\geq \binom{\omega-1}{2}+1\). Note that \(\binom{\omega-1}{2} \leq m_1\leq \binom{\omega-1}{2}+\delta\). If \(m_1=\binom{\omega-1}{2}\), then \(G[\Omega_1]\cong K_{\omega-1}\). By 18 , we have \(\rho_2<\rho_1(G[\Omega_1])=\omega-2\leq \frac{m-2}{\omega}.\) If \(m_1=\binom{\omega-1}{2}+1\) and \(G[\Omega_1] \not\cong K_{\omega}-e\) , then by Lemma 13, we have \(\rho_2<\rho_1(G[\Omega_1])<\omega-2+\frac{1}{\omega} \leq \frac{m-2}{\omega}.\) For \(G[\Omega_1]\cong K_\omega-e\), since \(m_1=\binom{\omega-1}{2}+1\) and \(e(K_\omega-e)=\binom{\omega}{2}-1\), we obtain that \(\omega=3\). Hence \(G[\Omega_1]\cong K_3-e\cong P_3\) and \(m_1=2\). Since \(m_1+r=\binom{3}{2}+1=4\), we have \(r=2\). If \(m_2\geq3\), then by 18 , \(\rho_2<\rho_1(G[\Omega_1])=\rho_1(P_3)=\sqrt2<\frac{5}{3} \leq \frac{m_2+2}{3} =\frac{m-2}{3}\). So it remains to consider \(m_2=2\). Since \(G[\Omega_2]\) is connected and has two edges, we have \(G[\Omega_2]\cong P_3\). Thus \(G\) is obtained from two copies of \(P_3\) by adding two edges between them. Since \(\omega(G)=3\), these two added edges must form a triangle together with one edge of one of the two paths. Up to isomorphism, there are only two types. Let \(P_3=x_1x_2x_3\) and \(P_3'=y_1y_2y_3\). The first type is \(H_1=P_3\cup P_3'+\{x_1y_1,x_1y_2\}\), and the second type is \(H_2=P_3\cup P_3'+\{x_2y_1,x_2y_2\}\). Their characteristic polynomials are given respectively by \[\begin{align} P(H_1;x)= x^6-6x^4-2x^3+7x^2+2x-1, \quad P(H_2;x)= x^2\left(x^4-6x^2-2x+5\right). \end{align}\] It follows that \(\rho_2(H_i)<\frac{4}{3}\). Since \(m=m_1+m_2+r=2+2+2=6\) and \(\omega=3\), we have \(\rho_2(G)<\frac{m-2}{\omega}=\frac{4}{3}\).

Therefore, in this subcase, we have \(\rho_2<\frac{m-2}{\omega}.\)

Subcase .. \(\kappa \leq \omega-2\).

Since \(\kappa \geq 1\), \(\omega\geq 3\). If \(\omega=3\), then \(\kappa = 1\), and hence each connected graph \(G[\Omega_i]\) is a single vertex. By 18 , this gives \(\rho_2\leq0\), contrary to our assumption \(\rho_2>0\). We may assume that \(\omega\geq4\).

Choose a maximum clique \(K_\omega\) of \(G\). Write \(a=|K_\omega\cap\Omega_1|\) and \(b=|K_\omega\cap\Omega_2|\). WLOG, we may assume that \(a\geq b\). Since \(Z=\emptyset\), we have \(a+b=\omega\). The \(ab\) edges of \(K_\omega\) joining \(K_\omega\cap\Omega_1\) and \(K_\omega\cap\Omega_2\) are not internal to any nodal domain. Then \(r\geq r_K= ab\). Since \(\kappa\leq\omega-2\), we also have \(a\leq\omega-2\). So \(b\geq2\). By 18 , Theorem 14, and Lemma 15, we have \[\begin{align} \rho_2^2 < \min\{\rho_1^2(G[\Omega_1]), \rho_1^2(G[\Omega_2])\} \leq \frac{(m-2)^2}{\omega^2}. \end{align}\]

Characterization of extremal graphs

For \(n\) is even, we know that \(2K_\omega+e\) attains the maximum value of \(\rho_2(G)\omega-e(G)\) from the preceding discussion; that is, this maximum is attained if and only if \(G\cong 2K_{\frac{n}{2}}+e\) with even \(n\).

For \(n\) is odd, we have \(\rho_2(G)\leq \frac{m-2}{\omega}\). The equality may hold only for the subcases \(\kappa=\omega\) and \(\kappa=\omega-1\) in Case [case:Z-nonempty].

In Subcase [subcase:Z-nonempty-kappa-omega] \(\kappa=\omega\), suppose that equality holds in 20 . Then \(m=\omega^2-\omega+2\), \(m_2=m-\binom{\omega}{2}-2=\binom{\omega}{2}\), and \(m_1+r=\binom{\omega}{2}+2\). Since \(\kappa=\omega\), the graph \(G[\Omega_1]\) contains a clique \(K_\omega\), which implies that \(m_1\geq \binom{\omega}{2}\). Note that \(r \geq 2\). Thus \(m_1=\binom{\omega}{2}\) and \(r=2\). Then \(G[\Omega_1]\cong K_\omega\). Moreover, since \(Z\neq\emptyset\) and \(G\) is connected, the equality \(r=2\) implies that \(Z\) consists of exactly one vertex, which is adjacent to both nodal domains. By Theorem 15 and the equality in 19 and 20 , we have \[\begin{align} \mu_1(G_{U_i})^2=\rho_1(G[\Omega_2])^2=\rho_1(G[\Omega_1])^2=(\omega-1)^2 \leq 2\binom{\omega}{2}-|\Omega_2|+1= \omega(\omega-1)-|\Omega_2|+1. \end{align}\] Then \(|\Omega_2|\leq \omega\). On the other hand, \(\binom{\omega}{2}=m_2\leq \binom{|\Omega_2|}{2}\), which implies \(|\Omega_2|\geq \omega\). Therefore, we have \(|\Omega_2|=\omega\) and \(G[\Omega_2]\cong K_\omega\). Then \(G\) is composed of two copies of \(K_\omega\) linked by a path of length two. Conversely, suppose that \(G\) is obtained from two disjoint copies \(K_\omega^{(1)}\) and \(K_\omega^{(2)}\) by adding a new vertex z and two edges \(zx_1\),\(zx_2\), where \(x_i\in V\bigl(K_\omega^{(i)}\bigr)\) for \(i=1,2\). Define a vector \(\mathbf{x}\in\mathbb{R}^{V(G)}\) by \[\begin{align} x_u= \begin{cases} 1, & u\in V\bigl(K_\omega^{(1)}\bigr),\\ -1, & u\in V\bigl(K_\omega^{(2)}\bigr),\\ 0, & u=z. \end{cases} \end{align}\] For any \(v\in V(K_\omega^{(i)})\), we have \((A(G)\mathbf{x})_v=(\omega-1)x_v\). For the vertex \(z\), we get \((A(G)\mathbf{x})_z=1+(-1)=0=(\omega-1)x_z\). Thus, \(\omega-1\) is an adjacency eigenvalue of \(G\). Since \(G\) is connected and \(K_\omega\) is a proper subgraph of \(G\), by Lemma 9, we have \(\rho_1(G)>\rho_1(K_\omega)=\omega-1\). It follows that \(\rho_2(G)\geq \omega-1\). Together with the bound \(\rho_2(G)\leq \frac{m-2}{\omega}=\omega-1\) already proved, we obtain \(\rho_2(G)=\omega-1=\frac{m-2}{\omega}\).

In Subcase [subcase:Z-nonempty-kappa-omega-1] \(\kappa=\omega-1\), suppose that equality holds in 21 . Then \(m=\omega^2-2\omega+2\), \(m_2=m-\binom{\omega-1}{2}-\omega=\binom{\omega-1}{2}\), \(m_1=\binom{\omega-1}{2}\), and \(r=\omega\). The selected clique \(K_\omega\) consists of \(z\) and \(\omega-1\) vertices of \(G[\Omega_1]\). Hence \(z\) is adjacent to all vertices of \(G[\Omega_1]\), contributing \(\omega-1\) edges. Since \(r=\omega\) and \(G\) is connected, there is exactly one more edge, which joins \(z\) to \(G[\Omega_2]\). In particular, \(Z=\{z\}\). Since \(\kappa=\omega-1\), we have \(G[\Omega_1]\cong K_{\omega-1}\). By Theorem 15 and the equality in 21 and 19 , we have \[\begin{align} \rho_1(G[\Omega_2])^2=\rho_1(G[\Omega_1])^2=(\omega-2)^2 \leq 2\binom{\omega-1}{2}-|\Omega_2|+1= (\omega-1)(\omega-2)-|\Omega_2|+1, \end{align}\] which implies \(|\Omega_2|\leq \omega-1\). On the other hand, \(\binom{\omega-1}{2}=m_2\leq \binom{|\Omega_2|}{2}\), which implies \(|\Omega_2|\geq \omega-1\). Hence \(|\Omega_2|=\omega-1\) and \(G[\Omega_2]\cong K_{\omega-1}\). Therefore, \(G\) is obtained from \(K_\omega\) and \(K_{\omega-1}\) by adding exactly one edge between them. The converse is similar to Subcase [subcase:Z-nonempty-kappa-omega] .

In conclusion, for odd \(n\), the equality holds if and only if \(G\) is composed of \(K_{\frac{n+1}{2}}\) and \(K_{\frac{n-1}{2}}\) linked by an edge, or \(K_{\frac{n-1}{2}}\) and \(K_{\frac{n-1}{2}}\) linked by a path.

The proof is complete. ◻