Proof. From 1([lem:p]), we obtain \(\ell \in \mathbb{N}^+\) such that \(P_\ell \not\in \mathcal{G}(\lambda)\). Clearly, for every nonempty \(A\), the path extensions \((C, A, \ell)\) and \((D, A, \ell)\), each of which contains \(P_\ell\) as a subgraph, are not in \(\mathcal{G}(\lambda)\). With hindsight, using 1([lem:c1], [lem:c2], [lem:n1], [lem:n2]), we choose \(m \in \mathbb{N}^+\) such that none of the following graphs \[\label{eqn:hoffman-extension} (C_3, V_2(C_3), \ell_0, K_m), (C_3, V_2(C_3), K_m), (\overline{K}_2, V(\overline{K}_2), \ell_0, K_m), (\overline{K}_2, V(\overline{K}_2), K_m),\tag{1}\] where \(\ell_0 \in \left\{{0, \dots, \ell + 1}\right\}\), is in \(\mathcal{G}(\lambda)\).

It suffices to prove that every clique extension and every path-clique extension in the extension families \(\mathcal{X}(C, \ell, m)\) and \(\mathcal{X}(D, \ell, m)\) contains one of the graphs in 1 as a subgraph. Label the vertices of \(C\) and \(D\) as in 4, and pick an arbitrary \(\ell_0 \in \left\{{0, \dots, \ell - 1}\right\}\). The clique extension \((C, A, K_m)\) and the path-clique extension \((C, A, \ell_0, K_m)\) respectively contain \[\begin{align} (\overline{K}_2, V(\overline{K}_2), 0, K_m) \text{ and } (\overline{K}_2, V(\overline{K}_2), \ell_0 + 1, K_m) & \text{ when } 0 \in A \text{ and }\abs{A \cap \left\{{1,2,3}\right\}} \le 1;\\ (\overline{K}_2, V(\overline{K}_2), 1, K_m) \text{ and } (\overline{K}_2, V(\overline{K}_2), \ell_0 + 2, K_m) & \text{ when } 0 \not\in A \text{ and }\abs{A \cap \left\{{1,2,3}\right\}} = 1;\\ (\overline{K}_2, V(\overline{K}_2), K_m) \text{ and } (\overline{K}_2, V(\overline{K}_2), \ell_0, K_m) & \text{ when } \abs{A \cap \left\{{1,2,3}\right\}} \ge 2, \end{align}\] and the clique extension \((D, A, K_m)\) and the path-clique extension \((D, A, \ell_0, K_m)\) respectively contain \[\begin{align} (\overline{K}_2, V(\overline{K}_2), 0, K_m) \text{ and } (\overline{K}_2, V(\overline{K}_2), \ell_0 + 1, K_m) & \text{ when } A \subseteq \left\{{0,2}\right\} \text{ and }A \neq \varnothing; \\ (C_3, V_2(C_3), 0, K_m) \text{ and } (C_3, V_2(C_3), \ell_0 + 1, K_m) & \text{ when } A \in \left\{{\left\{{1}\right\}, \left\{{3}\right\}}\right\}; \\ (\overline{K}_2, V(\overline{K}_2), K_m) \text{ and } (\overline{K}_2, V(\overline{K}_2), \ell_0, K_m) & \text{ when } A \supseteq \left\{{1,3}\right\}; \\ (C_3, V_2(C_3), K_m) \text{ and } (C_3, V_2(C_3), \ell_0, K_m) & \text{ when } \abs{A \cap \left\{{0,2}\right\}} \ge 1 \text{ and } \abs{A \cap \left\{{1,3}\right\}} = 1. \end{align}\] Therefore the extension families \(\mathcal{X}(C, \ell, m)\) and \(\mathcal{X}(D, \ell, m)\) are both disjoint from \(\mathcal{G}(\lambda)\). ◻

Proof. With hindsight, we choose \(N = vd^{\ell}\), where \(d\) is the Ramsey number \(R(k, 2^{v + 1}m + v)\), and \(v\) is the number of vertices of \(F\). Suppose that \(G\) is a connected graph with more than \(N\) vertices that contains no member in \(\left\{{S_k}\right\} \cup \mathcal{X}(F, \ell, m)\) as a subgraph. Assume for the sake of contradiction that the subgraph of \(G\) induced on a vertex subset, say \(V\), is isomorphic to \(F\).

Since \(G\) is a connected graph with more than \(vd^{\ell}\) vertices, we claim that either there exists a vertex \(u\) at distance at least \(\ell\) from \(V\), or the maximum degree of \(G\) is at least \(d\). Indeed, assume for the sake of contradiction that every vertex of \(G\) is within distance \(\ell-1\) from \(V\), and the maximum degree of \(G\) is less than \(d\). For \(i \in \left\{{0, 1, \dots, \ell-1}\right\}\), let \(V_i\) be the set of vertices of at distance \(i\) from \(V\). Clearly \(V_0 = V\), and so \(\abs{V_0} = v\). Using the assumption on the maximum degree of \(G\), one can inductively show that \(\abs{V_i} \le vd^i\). Therefore the number of vertices in \(G\) expressed as \(\sum_{i = 0}^{\ell - 1}\abs{V_i}\) is at most \(\sum_{i=0}^{\ell - 1}vd^i = v(d^\ell - 1)/(d-1) \le vd^\ell\), which yields a contradiction.

We break the rest of the proof into two cases.

Case 1: There exists a vertex \(u\) at distance at least \(\ell\) from \(V\). Thus the subgraph \(G[V]\) and a shortest path from \(V\) to \(u\) contains the path extension \((F, A, \ell)\) as a subgraph for some nonempty \(A \subseteq V\), which is a contradiction.

Case 2: The maximum degree of \(G\) is at least \(d\). Let \(u\) be a vertex of \(G\) with the maximum degree, and let \(N(u)\) be the set of neighbors of \(u\) in \(G\). Since \(S_k\) is not a subgraph of \(G\), the subgraph \(G[N(u)]\) cannot have an independent set of size \(k\). Because \(d = R(k, 2^{v + 1}m + v)\), the subgraph \(G[N(u)]\) contains a clique of order \(2^{v + 1}m + v\), and so there exists a clique \(G[U]\) of size \(2^{v + 1}m\) that is vertex-disjoint from \(F\).

We further partition the vertices in \(U\) as follows. For every subset \(A\) of \(V\), let \(U(A)\) be the set of vertices in \(U\) that are adjacent to all vertices in \(A\) and not adjacent to any vertex in \(V \setminus A\). By the pigeonhole principle, there exists a subset \(A\) of \(V\) such that \(\abs{U(A)} \ge 2m\). If \(A\) is nonempty, then \(G[V \cup U(A)]\) contains the clique extension \((F, A, K_m)\) as a subgraph, which is a contradiction.

Hereafter we may assume that \(\abs{U(\varnothing)} \ge 2m\), hence the distance between \(V\) and \(U(\varnothing)\) is at least \(2\). Let \(v_0 \dots v_{\ell_0}\) be a shortest path between \(V\) and \(U(\varnothing)\), where \(v_0\) and \(v_{\ell_0}\) are respectively at distance \(1\) from \(V\) and \(U(\varnothing)\). Let \(A_1\) be the nonempty set of vertices in \(V\) that are adjacent to \(v_0\), and denote by \(v_{\ell_0 + 1}\) an arbitrary vertex in \(U(\varnothing)\) that is adjacent to \(v_{\ell_0}\). We may assume that \(\ell_0 < \ell - 1\) because otherwise \(G[V \cup \left\{{v_0, \dots, v_{\ell_0}, v_{\ell_0 + 1}}\right\}]\) would contain the path extension \((F, A_1, \ell)\) as a subgraph, which is a contradiction. Let \(A_2\) be the nonempty set of vertices in \(U(\varnothing)\) that are adjacent to \(v_{\ell_0}\). If \(\abs{A_2} \ge m\), then \(G[V \cup \left\{{v_0, \dots, v_{\ell_0}}\right\} \cup A_2]\) contains the path-clique extension \((F, A_1, \ell_0, K_m)\) as a subgraph. Otherwise \(\abs{U(\varnothing) \setminus A_2} > m\), and so \(G[V \cup \left\{{v_0, \dots, v_{\ell_0}, v_{\ell_0 + 1}}\right\} \cup (U(\varnothing) \setminus A_2)]\) contains the path-clique extension \((F, A_1, \ell_0 + 1, K_m)\). ◻

Proof. We obtain \(\ell, m \in \mathbb{N}^+\) from 1 2 such that the following family \[\begin{align} \mathcal{F}_1 := & \left\{{S_4, P_\ell}\right\} \cup \mathcal{X}(C, \ell, m) \cup \mathcal{X}(D, \ell, m) \\ & \cup \left\{{(C_n, V_2(C_n), \ell_0, K_m)}\colon{n \in \left\{{3, \dots, \ell + 1}\right\}, \ell_0 \in \left\{{0, \dots, \ell - 1}\right\}}\right\} \\ & \cup \left\{{(C_n, V_2(C_n), K_m)}\colon{n \in \left\{{3, \dots, \ell + 1}\right\}}\right\} \\ & \cup \left\{{(K_m, V(K_m), \ell_0, K_m)}\colon{\ell_0 \in \left\{{0, \dots, \ell-1}\right\}}\right\} \end{align}\] is disjoint from \(\mathcal{G}(\lambda)\).

We obtain \(N_0\) from 3 such that for every connected graph \(G\) with more than \(N_0\) vertices, if no member in \(\left\{{S_4}\right\} \cup \mathcal{X}(C, \ell, m) \cup \mathcal{X}(D, \ell, m)\) is a subgraph of \(G\), then neither is \(C\) nor \(D\). With hindsight, we choose \(N = \max(N_0, (m+1)^{\ell+2})\). Suppose that \(G\) is a connected graph with more than \(N\) vertices, and suppose that no member in \(\mathcal{F}_1\) is a subgraph of \(G\). By our choice of \(N_0\), we know that neither \(C\) nor \(D\) is a subgraph of \(G\).

6 implies that \(G\) is the line graph of another connected graph, say \(H\). Since \(P_\ell\) is not a subgraph of \(G\), the path \(P_{\ell + 1}\) cannot be a general subgraph of \(H\). In particular, the diameter⁸ of \(H\) is at most \(\ell\). Let \(d\) be the maximum degree of \(H\). If \(d < m + 2\), then \(H\) has at most \((m+1)^{\ell+1}\) vertices, and at most \((m+1)^{\ell+2}\) edges, and so \(G\) has at most \((m+1)^{\ell+2}\) vertices, which is a contradiction.

We may assume that \(d \ge m + 2\). Let \(u\) be a vertex of \(H\) with degree \(d\). We claim that \(H\) is a tree. Suppose on the contrary that \(H\) contains a cycle as a general subgraph. Since \(H\) does not contain \(P_{\ell + 1}\) as a general subgraph, the length of any cycle in \(H\) cannot exceed \(\ell + 1\). Suppose in addition that \(u\) is on a cycle in \(H\). Let \(C_n\) be a shortest cycle containing \(u\), where \(n \in \left\{{3, \dots, \ell + 1}\right\}\). By the choice of \(C_n\), the vertex \(u\) has at least \(d - 2 \ge m\) neighbors outside \(C_n\). Thus \(H\) contains \(C_n\) with \(S_m\) attached at \(u\) as a general subgraph, and so \(G\) contains \((C_n, V_2(C_n), K_m)\) as a subgraph, which is a contradiction. Therefore \(u\) is not on any cycle in \(H\). Let \(C_n\) be any cycle in \(H\), where \(n \in \left\{{3, \dots, \ell + 1}\right\}\). Let \(P_{\ell_0}\) be a shortest path between \(u\) and \(C_n\), where \(\ell_0 \in \left\{{1, \dots, \ell}\right\}\). Since \(u\) is not on any cycle, \(u\) has at least \(d - 1 > m\) neighbors outside \(C_n\) and \(P_{\ell_0}\). Thus \(H\) contains \(C_n \cup P_{\ell_0}\) with \(S_m\) attached at \(u\) as a general subgraph, and so \(G\) contains \((C_n, V_2(C_n), \ell_0 - 1, K_m)\) as a subgraph, which is a contradiction.

We now view \(H\) as a tree rooted at \(u\). We claim that \(u\) is the only vertex with degree larger than \(m\). Suppose on the contrary that there is another vertex \(u'\) with degree at least \(m + 1\) in \(H\). Let \(P_{\ell_0}\) be a shortest path between \(u\) and \(u'\), where \(\ell_0 \in \left\{{1, \dots, \ell}\right\}\). Thus \(H\) contains \(P_{\ell_0}\) with two vertex-disjoint stars \(S_m\) respectively attached to \(u\) and \(u'\) as a (general) subgraph, and so \(G\) contains \((K_m, V(K_m), \ell_0 - 1, K_m)\) as a subgraph, which is a contradiction. Therefore all the vertices but \(u\) in \(H\) has degree at most \(m\). After the root \(u\) is removed from \(H\), each connected component has diameter at most \(\ell\) and degree at most \(m\), and so each connected component has at most \(m^{\ell+1} \le N\) vertices. ◻

Proof. Suppose that \(s_1, s_2, \dots\) is an infinite sequence of distinct tuples in \(\mathbb{N}^n\). For every \(i < j\), color the edge \(s_i s_j\) by \(0\) if \(s_i < s_j\), otherwise by any \(k \in \left\{{1, \dots, n}\right\}\) such that \(s_{i,k} > s_{j,k}\). The infinite Ramsey’s theorem provides an infinite subset \(I \subseteq \mathbb{N}^+\) such that the edges \(s_i s_j\), where \(i, j \in I\) and \(i\neq j\), all receive the same color \(c\). Because \((\mathbb{N}, \le)\) does not contain infinite descending chains, it must be the case that \(c = 0\). This implies that \(\left\{{s_i}\colon{i \in I}\right\}\) is an infinite ascending chain, and in particular \(\left\{{s_1, s_2, \dots}\right\}\) is not an antichain. ◻

Proof of 2 for \(\lambda< 2\). Let \(N \in \mathbb{N}\) and \(\mathcal{F}_1\) be given by 4, and set \[\begin{align} \mathcal{F}_0 & := \left\{{G \not\in \mathcal{G}(\lambda)}\colon{G \text{ has at most }N \text{ vertices}}\right\}, \\ \widetilde{\mathcal{F}}_2 & := \left\{{G \not\in \mathcal{G}(\lambda)}\colon{\exists H \in \mathcal{T}_N \text{ s.t.\;}G = L(H)}\right\}, \end{align}\] where \(\mathcal{T}_N\) is the family of rooted trees such that every connected component obtained from removing the root has at most \(N\) vertices. Setting \(\mathcal{F}_2\) to be the family of graphs that are minimal in \(\widetilde{\mathcal{F}}_2\) under taking subgraphs, one can check that \(\mathcal{F}_0 \cup \mathcal{F}_1 \cup \mathcal{F}_2\) is a forbidden subgraph characterization of \(\mathcal{G}(\lambda)\).

It suffices to prove that \(\mathcal{F}_2\) is finite. Let \(T_1, \dots, T_n\) be an enumeration of rooted trees on at most \(N\) vertices. We encode \(G \in \mathcal{F}_2\) by \(t_G \in \mathbb{N}^n\) as follows. Let \(H\) be the rooted tree in \(\mathcal{T}_N\) such that \(G = L(H)\). After removing the root \(u\) from \(H\), we view each connected component as a tree rooted at the vertex that is a child of \(u\) in \(H\). Set \(t_G := (t_1, \dots, t_n)\), where \(t_i\) is the number of occurrences of \(T_i\) as a connected component in the graph obtained by removing \(u\) from \(H\). Because no member of \(\mathcal{F}_2\) is a subgraph of any other, one can deduce that \(\left\{{t_G}\colon{G \in \mathcal{F}_2}\right\}\) is an antichain in \((\mathbb{N}^n, \le)\), and so \(\mathcal{F}_2\) is finite by 5. ◻

Proof of 2 for \(\lambda\in [2, \lambda^*)\) assuming 7. It is known that \(\mathcal{G}(2)\) has a finite forbidden subgraph characterization — in fact, there are \(1812\) minimal forbidden subgraphs for \(\mathcal{G}(2)\); see [1]. In view of 7, it suffices to show that if \(G\) is a minimal forbidden subgraph for \(\mathcal{G}(\lambda)\), then \(G\) is a minimal forbidden subgraph for \(\mathcal{G}(2)\), or \(G\), after removing some vertex, is a connected graph in \(\mathcal{G}(\lambda)\setminus \mathcal{G}(2)\).

Indeed, let \(G\) be a minimal forbidden subgraph for \(\mathcal{G}(\lambda)\). Because \(\lambda_1(G) < -\lambda\le -2\), the graph \(G\) contains a minimal forbidden subgraph for \(\mathcal{G}(2)\) as a subgraph, say \(F\). Clearly both \(G\) and \(F\) are connected. We may assume that \(F\) is a proper subgraph of \(G\) because otherwise we are done already. Consider the graph \(H\) obtained after removing \(v\) from \(G\), where \(v\) is a vertex of \(G\) that is furthest from \(F\). Using the connectivity of \(F\), one can then show that \(H\) is connected. Finally, \(H \in \mathcal{G}(\lambda)\) because of the minimality of \(G\), and \(H \not\in \mathcal{G}(2)\) because \(F\) is a subgraph of \(H\). ◻

Proof of 1 for \(\lambda\in (2,\lambda^*)\). It follows immediately from 7 that \(-\lambda\) is not a limit point of the set of smallest eigenvalues of graphs for \(\lambda\in (2,\lambda^*)\) ◻

Proof. Pick \(\ell_0 \in \mathbb{N}\) such that \(\lambda_1(F, A, \ell) < -\lambda\) for every \(\ell \ge \ell_0\). Clearly \(\lambda_1(F, A, \ell, K_m) < -\lambda\) for every \(\ell \ge \ell_0\) and every \(m \in \mathbb{N}^+\). It suffices to show that for every \(\ell \in \left\{{0, \dots, \ell_0 - 1}\right\}\) there exists \(m \in \mathbb{N}^+\) such that \(\lambda_1(F, A, \ell, K_m) < -\lambda\).

Let \(v_0 \dots v_{\ell_0}\) be the path added to \(F\) to obtain \((F, A, \ell_0)\), where the vertex \(v_0\) is connected to every vertex in \(A\). Set \(\lambda_0 := -\lambda_1(F, A, \ell_0)\), and let \(\boldsymbol{x}\colon V(F) \cup \left\{{v_0, \dots, v_{\ell_0}}\right\} \to \mathbb{R}\) be an eigenvector of \((F, A, \ell_0)\) associated with \(-\lambda_0\).

Now fix \(\ell \in \mathbb{N}\) with \(\ell < \ell_0\), and let \(m \in \mathbb{N}^+\) be determined later. Set \(V_\ell := V(F) \cup \left\{{v_0, \dots, v_\ell}\right\}\), and identify the vertex set of \((F, A, \ell, K_m)\) with \(V_\ell \cup V(K_m)\). We abuse notation and write \(x_i\) in place of \(x_{v_i}\) for \(i \in \left\{{\ell, \dots, \ell_0}\right\}\). Define \(\tilde{\boldsymbol{x}}\colon V_\ell \cup V(K_m) \to \mathbb{R}\) by \[\tilde{x}_v = \begin{cases} x_v & \text{if }v \in V_\ell; \\ x_{\ell+1}/m & \text{if }v \in V(K_m). \end{cases}\]

We claim that \(\sum_{v \in V_\ell}x_v^2 > 0\). Indeed, assume for the sake of contradiction that \(x_v = 0\) for \(v \in V_\ell\). Using \(-\lambda_0x_i = \sum_{u\sim v_i}x_u\) for \(i \in \left\{{\ell, \dots, \ell_0-1}\right\}\), where the sum is taken over all vertices \(u\) that are adjacent to the vertex \(v_i\) in \((F, A, \ell_0)\), one can prove inductively that \(x_i = 0\) for \(i \in \left\{{\ell + 1, \dots, \ell_0}\right\}\), which contradicts the assumption that \(\boldsymbol{x}\) is a nonzero vector.

Because \(\sum_{v \in V_\ell} x_v^2 > 0\), clearly \(\tilde{\boldsymbol{x}}\) is a nonzero vector. We compute \[\tilde{\boldsymbol{x}}^\intercal \tilde{\boldsymbol{x}}= \sum_{v \in V_\ell}x_v^2 + m(x_{\ell + 1}/m)^2.\] Moreover we can compute \(\tilde{\boldsymbol{x}}^\intercal A_{(F, A, \ell, K_m)} \tilde{\boldsymbol{x}}\) as follows \[\tilde{\boldsymbol{x}}^\intercal A_{(F, A, \ell, K_m)} \tilde{\boldsymbol{x}}= \sum_{u, v \in V_\ell\colon u \sim v} x_ux_v + 2x_\ell x_{\ell+1} + m(m-1)(x_{\ell+1}/m)^2.\] Since \(\boldsymbol{x}\) is an eigenvector of \((F, A, \ell_0)\) associated with \(-\lambda_0\), we obtain that \[\sum_{u, v \in V_\ell\colon u \sim v} x_ux_v + x_\ell x_{\ell + 1} = \sum_{v \in V_\ell}x_v\sum_{u \sim v}x_u = -\lambda_0 \sum_{v \in V_\ell}x_v^2.\] Thus \(\tilde{\boldsymbol{x}}^\intercal A_{(F, A, \ell, K_m)} \tilde{\boldsymbol{x}}\) can be simplified to \[\tilde{\boldsymbol{x}}^\intercal A_{(F, A, \ell, K_m)} \tilde{\boldsymbol{x}}= -\lambda_0 \sum_{v \in V_\ell}x_v^2 + x_\ell x_{\ell+1} + m(m-1)(x_{\ell+1}/m)^2.\] The Rayleigh principle says that \(\lambda_1(F, A, \ell, K_m)\) is at most \[\frac{-\lambda_0 \sum_{v \in V_\ell} x_v^2 + x_\ell x_{\ell+1} + m(m-1)(x_{\ell+1}/m)^2}{\sum_{v \in V_\ell}x_v^2 + m(x_{\ell + 1}/m)^2},\] which, as \(m \to \infty\), approaches \[-\lambda_0 + \frac{(x_\ell + x_{\ell+1})x_{\ell+1}}{\sum_{v \in V_\ell}x_v^2}.\] Here we used the above claim that the denominator in the limit is positive.

Recall that \(\lambda_0 = -\lambda_1(F, A, \ell_0) > \lambda\ge 2\). It suffices to show that \((x_\ell + x_{\ell+1})x_{\ell+1} \le 0\). In fact, we prove inductively that \((x_i + x_{i+1})x_{i+1} \le 0\) for \(i \in \left\{{\ell, \dots, \ell_0 - 1}\right\}\). The base case where \(i = \ell_0 - 1\) follows immediately from \(-\lambda_0x_{\ell_0} = x_{\ell_0-1}\) and \(\lambda_0 > 2\). For the inductive step, using \(-\lambda_0x_{i+1} = x_i + x_{i+2}\) and \(\lambda_0 > 2\), we obtain \[\begin{gather} (x_i + x_{i+1})x_{i+1} = (-\lambda_0x_{i+1} - x_{i+2} + x_{i+1})x_{i+1} = -(\lambda_0 - 2)x_{i+1}^2 - (x_{i+1}+x_{i+2})x_{i+1} \\ \le -(x_{i+1}+x_{i+2})x_{i+1} = -(x_{i+1}+x_{i+2})^2 + (x_{i+1}+x_{i+2})x_{i+2} \le (x_{i+1}+x_{i+2})x_{i+2}, \end{gather}\] which is nonpositive by the inductive hypothesis. ◻

Proof of 7. Suppose that \(\lambda\in [2, \lambda^*)\). Let \(\mathcal{F}\) denote the set of minimal forbidden subgraphs for the family \(\mathcal{D}_\infty\). Combining 6 7, we choose \(\ell, m \in \mathbb{N}^+\) such that for every \(F \in \mathcal{F}\), the extension family \(\mathcal{X}(F, \ell, m)\) is disjoint from \(\mathcal{G}(\lambda)\). From 1([lem:s]), we know that \(S_5 \not\in \mathcal{G}(\lambda)\). In particular, no graph in \(\mathcal{G}(\lambda)\) contains any member in the following family \[\label{eqn:main1-2} \left\{{S_5}\right\} \cup \bigcup_{F \in \mathcal{F}} \mathcal{X}(F, \ell, m)\tag{2}\] as a subgraph. Using 3, we obtain \(N \in \mathbb{N}\) such that for every connected graph \(G\) with more than \(N\) vertices, if no member in 2 is a subgraph of \(G\), then neither is any \(F \in \mathcal{F}\), and so \(G\) is a generalized line graph and is in \(\mathcal{G}(2)\) by 9 8. This implies that every connected graph in \(\mathcal{G}(\lambda)\setminus \mathcal{G}(2)\) has at most \(N\) vertices. ◻

Proof of 2 for \(\lambda\ge \lambda^*\). 12 implies that \(\lim_+\Lambda_1 \supseteq [\lambda^*, \infty)\), which implies through 11 that \(\mathcal{G}(\lambda)\) has no finite forbidden subgraph characterization for any \(\lambda\ge \lambda^*\). ◻

Proof of 1 for \(\lambda\ge \lambda^*\). It follows immediately from 12 that \(-\lambda\) is a limit point of the set of smallest eigenvalues of graphs for \(\lambda\ge \lambda^*\). ◻

Proof of [lem:rowing-0]. Set \(\boldsymbol{a}= (a_1, \dots, a_n)\) and \(\lambda= \lambda_1(R(\boldsymbol{a}))\). Let \(v_{-2} \dots v_n\) denote the central path of \(R(\boldsymbol{a})\), and let \(v_c\) denote the coxswain attached to \(v_0\). Let \(\boldsymbol{x}\colon V(R(\boldsymbol{a})) \to \mathbb{R}\) be a unit eigenvector of \(R(\boldsymbol{a})\) associated with \(\lambda\). Clearly we have \(\lambda x_c = x_0\), which implies that \[\label{eqn:rowing-0} x_c^2 = \frac{x_c^2 + x_0^2}{1+\lambda^2} \le \frac{1}{1+\lambda^2}.\tag{3}\] Let \(L\) be the rowing graph \(R(\boldsymbol{a})\) with \(v_c\) removed, and let \(\boldsymbol{x}_L\) be \(\boldsymbol{x}\) restricted to \(V(L)\). Notice that \(L\) is a line graph of a caterpillar tree, and so \(\lambda_1(L) \ge -2\) (see 1 on ). Finally, we bound the smallest eigenvalue of \(R(\boldsymbol{a})\) as follows: \[\begin{gather} \lambda= \boldsymbol{x}^\intercal A_{R(\boldsymbol{a})} \boldsymbol{x}= \boldsymbol{x}_L^\intercal A_L \boldsymbol{x}_L + 2x_cx_0 \ge -2\boldsymbol{x}_L^\intercal \boldsymbol{x}_L + 2x_cx_0 \\ = -2(1-x_c^2) + 2\lambda x_c^2 = -2+(2+2\lambda)x_c^2 \stackrel{\eqref{eqn:rowing-0}}{\ge} -2 + \frac{2+2\lambda}{1+\lambda^2}, \end{gather}\] which implies that \(\lambda\ge -1-\sqrt{2}\). In the above inequality, we assumed that \(\lambda\le -1\) which follows from the fact that \(R(\boldsymbol{a})\) has an edge. ◻

Proof of [lem:rowing-a]. Let \(\boldsymbol{x}\) be the vector that assigns \(1\) to \(v_{-2}\), \(-2\) to \(v_{-1}\), \(4\) to \(v_0\), \(0\) to \(v_1\), \(-2\) to the coxswain, and \(-4/a_1\) to every vertex in the clique of size \(a_1\). The Rayleigh principle says that \(\lambda_1(R(a_1))\) is at most \[\frac{\boldsymbol{x}^\intercal A_{R(a_1)} \boldsymbol{x}}{\boldsymbol{x}^\intercal \boldsymbol{x}} = \frac{-2(1 \cdot 2 + 2 \cdot 4 + 4 \cdot 2 + a_1 \cdot 4 \cdot (4/a_1)) + a_1(a_1-1) \cdot (-4/a_1)^2}{1^2 + (-2)^2 + 4^2 + (-2)^2 + a_1 \cdot (-4/a_1)^2},\] which approaches \(-52/25 = -2.08\) as \(a_1 \to \infty\). ◻

Proof of [lem:rowing-b]. Take \(\ell = \lceil 2/\varepsilon\rceil + 5\). Let \(v_{-2} \dots v_{n_1 + \ell + n_2}\) denote the central path of the rowing graph \(R(\boldsymbol{a}, 0^{(\ell)}, \boldsymbol{b})\), where \(\boldsymbol{a}= (a_1, \dots, a_{n_1})\) and \(\boldsymbol{b}= (b_1, \dots, b_{n_2})\), and let \(\boldsymbol{x}\colon V(R(\boldsymbol{a},0^{(\ell)},\boldsymbol{b})) \to \mathbb{R}\) be a unit eigenvector of \(R(\boldsymbol{a},0^{(\ell)},\boldsymbol{b})\) associated with the smallest eigenvalue. Choose \(k \in \left\{{0, \dots, \ell - 1}\right\}\) such that \(x_{n_1+k}x_{n_1+k+1}\) reaches the minimum in absolute value. In particular, using the inequality \(\abs{x_{n_1+i}x_{n_1+i+1}} \le (x_{n_1+i}^2 + x_{n_1+i+1}^2)/2\), we obtain \[\label{eqn:rowing-b} \abs{x_{n_1+k}x_{n_1+k+1}} \le \frac{1}{\ell}\sum_{i = 0}^{\ell - 1}\abs{x_{n_1+i}x_{n_1+i+1}} \le \frac{1}{\ell} \sum_{i=0}^{\ell}x_{n_1+i}^2 \le \frac{1}{\ell} < \frac{\varepsilon}{2}.\tag{4}\]

Notice that removing the edge \(v_{n_1+k} v_{n_1+k+1}\) disconnects \(R(\boldsymbol{a},0^{(\ell)},\boldsymbol{b})\) into two subgraphs, one of which is \(R(\boldsymbol{a}, 0^{(k)})\), while the other is a line graph, denoted \(L\), of a caterpillar tree. Clearly \[\label{eqn:rowing-b-1} \lambda_1(R(\boldsymbol{a}, 0^{(k)})) \ge \lambda_1(R(\boldsymbol{a}, 0^{(\ell)})).\tag{5}\] As \(\ell \ge 6\), the graph \(\widetilde{E}_8\) in 1 is a proper subgraph of \(R(\boldsymbol{a}, 0^{(\ell)})\), and so \(\lambda_1(R(\boldsymbol{a}, 0^{(\ell)})) < -2\). Together with \(\lambda_1(L) \ge -2\) (see 1 on ), we obtain \[\label{eqn:rowing-b-2} \lambda_1(L) > \lambda_1(R(\boldsymbol{a}, 0^{(\ell)})).\tag{6}\] Let \(\boldsymbol{x}_R\) and \(\boldsymbol{x}_L\) be the unit eigenvector \(\boldsymbol{x}\) restricted to \(V(R(\boldsymbol{a},0^{(k)}))\) and \(V(L)\). Finally, we bound the smallest eigenvalue of \(R(\boldsymbol{a},0^{(\ell)},\boldsymbol{b})\) as follows: \[\begin{align} \lambda_1(R(\boldsymbol{a},0^{(\ell)},\boldsymbol{b})) & \stackrel{\phantom{(\ref{eqn:rowing-b},\ref{eqn:rowing-b-1},\ref{eqn:rowing-b-2})}}{=} \boldsymbol{x}^\intercal A_{R(\boldsymbol{a},0^{(\ell)},\boldsymbol{b})}\boldsymbol{x}\\ & \stackrel{\phantom{(\ref{eqn:rowing-b},\ref{eqn:rowing-b-1},\ref{eqn:rowing-b-2})}}{=} \boldsymbol{x}_R^\intercal A_{R(\boldsymbol{a},0^{(k)})} \boldsymbol{x}_R + 2x_{n_1+k}x_{n_1+k+1} + \boldsymbol{x}_L^\intercal A_L\boldsymbol{x}_L \\ & \stackrel{\phantom{(\ref{eqn:rowing-b},\ref{eqn:rowing-b-1},\ref{eqn:rowing-b-2})}}{\ge} \lambda_1(R(\boldsymbol{a},0^{(k)})) \boldsymbol{x}_R^\intercal \boldsymbol{x}_R + 2x_{n_1+k}x_{n_1+k+1} + \lambda_1(L)\boldsymbol{x}_L^\intercal \boldsymbol{x}_L \\ & \stackrel{(\ref{eqn:rowing-b},\ref{eqn:rowing-b-1},\ref{eqn:rowing-b-2})}{>} \lambda_1(R(\boldsymbol{a},0^{(\ell)}))(\boldsymbol{x}_R^\intercal \boldsymbol{x}_R + \boldsymbol{x}_L^\intercal \boldsymbol{x}_L) - \varepsilon\\ & \stackrel{\phantom{(\ref{eqn:rowing-b},\ref{eqn:rowing-b-1},\ref{eqn:rowing-b-2})}}{=} \lambda_1(R(\boldsymbol{a}, 0^{(\ell)})) - \varepsilon. \qedhere \end{align}\] ◻

Proof of [lem:rowing-c]. Set \(\boldsymbol{a}= (a_1, \dots, a_n, 0^{(\ell)})\) and \(\lambda= \lambda_1(R(\boldsymbol{a}))\). Let \(\boldsymbol{x}\colon V(R(\boldsymbol{a})) \to \mathbb{R}\) be an eigenvector of \(R(\boldsymbol{a})\) associated with \(\lambda\). Let \(v_{-2}\dots v_{n + \ell}\) denote the central path of the rowing graph \(R(\boldsymbol{a})\). In \(R(\boldsymbol{a})\), let \(K\) denote the clique of size \(a_n\) attached to both \(v_{n-1}\) and \(v_n\), and pick an arbitrary vertex \(u\) from \(K\). We clearly have \[\label{eqn:rowing-c-0} \begin{align} \lambda x_u & = x_{n-1} + \sigma + x_n, \\ \lambda x_n & = x_{n-1} + \sigma + x_u + x_{n+1}, \end{align}\tag{7}\] where \(\sigma = \sum_{u' \in V(K) \setminus \left\{{u}\right\}} x_{u'}\).The above identities imply that \(\lambda(x_u - x_n) = x_n - x_u - x_{n+1}\), and so \[\label{eqn:rowing-c-1} x_u = x_n - \frac{x_{n+1}}{1 + \lambda}.\tag{8}\]

Let \(R(\tilde{\boldsymbol{a}})\) be the rowing graph obtained from \(R(\boldsymbol{a})\) by removing \(u\) and attaching a clique, denoted \(\tilde{K}\), to both \(v_n\) and \(v_{n+1}\), where \(\tilde{\boldsymbol{a}}= (a_1, \dots, a_n-1,a_{n+1},0^{(\ell-1)})\), and the order \(a_{n+1}\) of \(\tilde{K}\) is chosen later. In particular, \(V(R(\tilde{\boldsymbol{a}})) = V(R(\boldsymbol{a})) \setminus \left\{{u}\right\} \cup V(\tilde{K})\).

We define a vector \(\tilde{\boldsymbol{x}}\colon V(R(\tilde{\boldsymbol{a}}))\to\mathbb{R}\) as follows: \[\tilde{x}_v = \begin{cases} x_n + x_u & \text{if } v = v_n; \\ -(x_n + x_u + x_{n+1})/a_{n+1} & \text{if } v \in V(\tilde{K}); \\ x_v & \text{otherwise}. \end{cases}\] Because \(\boldsymbol{x}\) is a nonzero vector, one can check that so is \(\tilde{\boldsymbol{x}}\). We compute \[\tilde{\boldsymbol{x}}^\intercal \tilde{\boldsymbol{x}}= \boldsymbol{x}^\intercal \boldsymbol{x}- x_n^2 - x_u^2 + (x_n + x_u)^2 + \frac{(x_n + x_u + x_{n+1})^2}{a_{n+1}}.\] Moreover we can compare \(\tilde{\boldsymbol{x}}^\intercal A_{R(\tilde{\boldsymbol{a}})} \tilde{\boldsymbol{x}}\) and \(\boldsymbol{x}^\intercal A_{R(\boldsymbol{a})} \boldsymbol{x}\) as follows \[\begin{gather} \tilde{\boldsymbol{x}}^\intercal A_{R(\tilde{\boldsymbol{a}})} \tilde{\boldsymbol{x}}= \boldsymbol{x}^\intercal A_{R(\boldsymbol{a})} \boldsymbol{x}- 2x_u\left(x_{n-1} + \sigma + x_n\right) + 2x_u\left(x_{n-1} + \sigma + x_{n+1} \right) \\ - 2(x_n + x_u + x_{n+1})^2 + a_{n+1}(a_{n+1}-1)\left(\frac{x_n + x_u + x_{n+1}}{a_{n+1}}\right)^2, \end{gather}\] which simplifies via 7 to \[\tilde{\boldsymbol{x}}^\intercal A_{R(\tilde{\boldsymbol{a}})} \tilde{\boldsymbol{x}}= \lambda\boldsymbol{x}^\intercal \boldsymbol{x}- 2\lambda x_u^2 + 2x_u (\lambda x_n - x_u) - \left(1 + \frac{1}{a_{n+1}}\right)(x_n + x_u + x_{n+1})^2.\] The Rayleigh principle says that \(\lambda_1(R(\tilde{\boldsymbol{a}}))\) is at most \[\frac{\tilde{\boldsymbol{x}}^\intercal A_{R(\tilde{\boldsymbol{a}})} \tilde{\boldsymbol{x}}}{\tilde{\boldsymbol{x}}^\intercal \tilde{\boldsymbol{x}}} = \frac{\lambda\boldsymbol{x}^\intercal \boldsymbol{x}- 2\lambda x_u^2 + 2x_u (\lambda x_n - x_u) - \left(1 + 1/a_{n+1}\right)(x_n + x_u + x_{n+1})^2}{\boldsymbol{x}^\intercal \boldsymbol{x}- x_n^2 - x_u^2 + (x_n + x_u)^2 + (x_n + x_u + x_{n+1})^2/a_{n+1}},\] which, as \(a_{n+1} \to \infty\), approaches \[\frac{\lambda\boldsymbol{x}^\intercal \boldsymbol{x}- 2\lambda x_u^2 + 2x_u(\lambda x_n - x_u) - (x_n + x_u + x_{n+1})^2}{\boldsymbol{x}^\intercal \boldsymbol{x}- x_n^2 - x_u^2 + (x_n + x_u)^2}.\] Here we assumed that the denominator in the limit is nonzero. Indeed, suppose on the contrary that \(\boldsymbol{x}^\intercal \boldsymbol{x}= x_n^2 + x_u^2 - (x_n + x_u)^2 = -2x_nx_u\). Because \(-2x_nx_u \le x_n^2 + x_u^2 \le x_n^2 + x_u^2 + x_{n+1}^2 \le \boldsymbol{x}^\intercal \boldsymbol{x}\), it must be the case that \(x_n + x_u = 0\) and \(x_{n+1} = 0\). In view of 8 , we have \(x_n = x_u = 0\) and hence \(\boldsymbol{x}= \boldsymbol{0}\), which is a contradiction.

It suffices to prove that \[\lambda\boldsymbol{x}^\intercal \boldsymbol{x}- 2\lambda x_u^2 + 2x_u(\lambda x_n - x_u) - (x_n + x_u + x_{n+1})^2 \le \lambda\left( \boldsymbol{x}^\intercal \boldsymbol{x}- x_n^2 - x_u^2 + (x_n + x_u)^2 \right),\] which is equivalent to \[(x_n+x_u+x_{n+1})^2 + 2(1+\lambda)x_u^2 \ge 0.\] Using 8 , we know that the left hand side of the last inequality is equal to \[\begin{gather} \left(2x_n + \frac{\lambda}{1+\lambda}x_{n+1}\right)^2 + 2(\lambda+1)\left(x_n-\frac{x_{n+1}}{1+\lambda}\right)^2 \\ = (2\lambda+ 6)x_n^2 - \frac{4}{1+\lambda}x_nx_{n+1}+\left(1+\frac{1}{(1+\lambda)^2}\right)x_{n+1}^2. \end{gather}\] From 8[lem:rowing-0], we know that \(\lambda\ge -1-\sqrt{2}\) in addition to the assumption that \(\lambda\le -2\). One can check \[1 + \frac{1}{(1+\lambda)^2} \ge 2\lambda+ 6 \ge \frac{4}{1+\lambda}\cdot \frac{1}{\lambda} > 0, \quad \text{for }\lambda\in [-1-\sqrt2,-2].\]

We are left to prove \(x_n^2 - \lambda x_nx_{n+1} + x_{n+1}^2 \ge 0\). In fact, we prove inductively that \(x_i^2 - \lambda x_ix_{i+1} + x_{i+1}^2 \ge 0\) for \(i \in \left\{{n, \dots, n + \ell - 1}\right\}\). The base case where \(i = n + \ell - 1\) follows immediately from \(\lambda x_{n+\ell} = x_{n+\ell-1}\). For the inductive step, using \(\lambda x_{i+1} = x_i + x_{i+2}\), we obtain \[x_i^2 - \lambda x_i x_{i+1} + x_{i+1}^2 = (\lambda x_{i+1}-x_{i+2})^2 - \lambda(\lambda x_{i+1}-x_{i+2})x_{i+1} + x_{i+1}^2 = x_{i+1}^2 - \lambda x_{i+1}x_{i+2} + x_{i+2}^2,\] which is nonnegative by the inductive hypothesis. ◻

Proof of [lem:rowing-d]. Take \(m = \lceil 5/\varepsilon\rceil + 1\). Let \(v_{-2} \dots v_n\) denote the central path of the rowing graph \(R(\boldsymbol{a})\), where \(\boldsymbol{a}= (a_1, \dots, a_n)\), and let \(\boldsymbol{x}\colon V(R(\boldsymbol{a})) \to \mathbb{R}\) be a unit eigenvector associated with the smallest eigenvalue of \(R(\boldsymbol{a})\). Choose \(k \in \left\{{1, \dots, m}\right\}\) such that \(x_{k-1}\) reaches the minimum in absolute value. In particular, \[\label{eqn:rowing-d} x_{k-1}^2 \le \frac{1}{m} \sum_{i=0}^{m-1}x_i^2 \le \frac{1}{m} < \frac{\varepsilon}{5}.\tag{9}\]

Let \(v_{-2} \dots v_{k-1}v_* v_{k} \dots v_n\) denote the central path of \(R(\tilde{\boldsymbol{a}})\), where \(\tilde{\boldsymbol{a}}= (a_1, \dots, a_{k-1},0,a_{k}, \dots, a_n)\). We naturally view the vertex set of \(R(\tilde{\boldsymbol{a}})\) as \(V(R(\boldsymbol{a})) \cup \{ v_*\}\), and we extend the unit eigenvector \(\boldsymbol{x}\colon V(R(\boldsymbol{a})) \to \mathbb{R}\) to \(\tilde{\boldsymbol{x}}\colon V(R(\tilde{\boldsymbol{a}})) \to \mathbb{R}\) by setting \(\tilde{x}_* = x_{k-1}\). The Rayleigh principle says that \(\lambda_1(R(\tilde{\boldsymbol{a}}))\) is at most \[\begin{gather} \frac{\tilde{\boldsymbol{x}}^\intercal A_{R(\tilde{\boldsymbol{a}})} \tilde{\boldsymbol{x}}}{\tilde{\boldsymbol{x}}^\intercal \tilde{\boldsymbol{x}}} = \frac{\boldsymbol{x}^\intercal A_{R(\boldsymbol{a})} \boldsymbol{x}+ 2x_{k-1}^2}{\boldsymbol{x}^\intercal \boldsymbol{x}+ x_{k-1}^2} = \frac{\lambda_1(R(\boldsymbol{a})) + 2x_{k-1}^2}{1 + x_{k-1}^2} \\ = \lambda_1(R(\boldsymbol{a})) + \frac{(2-\lambda_1(R(\boldsymbol{a})))x_{k-1}^2}{1+x_{k-1}^2} \le \lambda_1(R(\boldsymbol{a})) + (2-\lambda_1(R(\boldsymbol{a})))x_{k-1}^2. \end{gather}\] From 8[lem:rowing-0], we obtain \[(2-\lambda_1(R(\boldsymbol{a})))x_{k-1}^2 \le (2 + (1 + \sqrt2))x_{k-1}^2 \stackrel{\eqref{eqn:rowing-d}}{<} \varepsilon. \qedhere\] ◻

Proof of 12. In view of 13, we may assume that \(\lambda\in (\lambda^*, \lambda')\). Fix \(\varepsilon> 0\). We assume for the sake of contradiction that no rowing graph has its smallest eigenvalue in \((-\lambda- \varepsilon, -\lambda)\) because otherwise we are done. Define \[\begin{gather} S := \left\{{(a_1, \dots, a_n) \in \mathbb{N}^n}\colon{n \in \mathbb{N}^+ \text{ and } a_n > 0}\right\}, \\ A := \left\{{(a_1, \dots, a_n) \in S}\colon{\lambda_1(R(a_1, \dots, a_n, 0^{(\ell)})) < -\lambda\text{ for some }\ell \in \mathbb{N}}\right\}. \end{gather}\]

Finally, let \(m\) be given by 8[lem:rowing-d]. The claim provides \((a_1, \dots, a_n) \in A\) with \(m\) nonzero entries such that 10 holds. Let \(\ell \in \mathbb{N}\) be such that \[\lambda_1(R(a_1, \dots, a_n, 0^{(\ell)})) < -\lambda.\] Since the length of \((a_1, \dots, a_n, 0^{(\ell)})\) is at least \(m\), 8[lem:rowing-d] says that there exists \(k \in \left\{{1, \dots, m}\right\}\) such that \[\lambda_1(R(a_1, \dots, a_{k-1}, 0, a_k, \dots, a_n, 0^{(\ell)})) < \lambda_1(R(a_1, \dots, a_n, 0^{(\ell)})) + \varepsilon,\] However 10 asserts that \((a_1, \dots, a_{k-1}, 0, a_k, \dots, a_n) \not\in A\), which implies that \[\lambda_1(R(a_1, \dots, a_{k-1}, 0, a_k, \dots, a_n, 0^{(\ell)})) \ge -\lambda.\] Combining the last three inequalities, we obtain that \[-\lambda- \varepsilon< \lambda_1(R(a_1,\dots, a_n, 0^{(\ell)})) < -\lambda. \qedhere\] ◻

Proof. Let \(v_0,v_1,\dots, v_{n-1}\) be the vertices of \(C_n^\pm\), and let \(\sigma\colon E(C^\pm_n) \to \left\{{\pm 1}\right\}\) be the signing of \(C^\pm_n\). Suppose that \(A^\pm\) is a signed set of \(\left\{{v_0,v_{n-1}}\right\}\). By switching a suitable subset of \(\left\{{v_0, v_{n-1}}\right\}\), we may assume that \(A^\pm = \{v_0^+, v_{n-1}^+\}\). If \(C_n^\pm\) has an even number of positive edges, then \(C^\pm_n\) is already switching equivalent to the all-negative cycle of length \(n\), whose smallest eigenvalue is \(-2\). If the edge \(v_0v_{n-1}\) is negative, then both \((C_n^\pm, A^\pm, \ell, K_m)\) and \((C_n^\pm, A^\pm, K_m)\) contain a subgraph that is switching equivalent to the all-negative triangle \(-K_3\), and so their smallest eigenvalues are at most \(\lambda_1(-K_3) = -2\).

Hereafter we assume that \(C_n^\pm\) has an odd number of positive edges, and the edge \(v_0v_{n-1}\) is positive. Furthermore, by switching a suitable subset of \(\left\{{v_1, \dots, v_{n-2}}\right\}\), we may assume that \(v_0v_{n-1}\) is the only positive edge of the signed cycle \(C_n^\pm\).

For ([lem:c1s]), we define a vector \(\boldsymbol{x}\colon V(C_n^\pm, A^\pm, \ell, K_m) \to \mathbb{R}\) as follows. Let \(v_{n}v_{n+1}\dots v_{n+\ell}\) and \(K_m\) be the path and the clique added to \(C_n^\pm\) to obtain the path-clique extension \((C_n^\pm, A^\pm, \ell, K_m)\), where \(v_{n}\) is adjacent to \(v_0\) and \(v_{n-1}\), and \(v_{n+\ell}\) is adjacent to every vertex in \(K_m\). Assign \(x_{v_i} = -1\) for \(i \in \left\{{0, \dots, n-1}\right\}\), \(x_{v_{n+i}} = 2(-1)^i\) for \(i \in \left\{{0, \dots, \ell}\right\}\), and \(x_u = -x_{n+\ell}/m\) for every \(u \in V(K_m)\). We abuse notation and write \(x_i\) in place of \(x_{v_i}\) for \(i \in \left\{{0, \dots, n+\ell}\right\}\). The Rayleigh principle says that the smallest eigenvalue of \((C_n^\pm, A^\pm, \ell, K_m)\) is at most \[\begin{gather} \bigg(-2\sum_{i=0}^{n-2}x_ix_{i+1} + 2x_0x_{n-1} + 2(x_0 + x_{n-1})x_n + 2\sum_{i=0}^{\ell-1}x_{n+i}x_{n+i+1} - 2x_{n+\ell}^2 + \\ + m(m-1)(x_{n+\ell}/m)^2\bigg) \bigg/ \bigg(\sum_{i=0}^{n-1} x_i^2 + \sum_{i=0}^\ell x_{n+i}^2 + m(x_{n+\ell}/m)^2\bigg), \end{gather}\] which is equal to \((-2n - 8(\ell+1) - 4/m)/(n + 4(\ell+1) + 4/m)\), and approaches \(-2\) as \(m \to \infty\).

For ([lem:c2s]), we define a vector \(\boldsymbol{x}\colon V(C_n^\pm, A^\pm, K_m) \to \mathbb{R}\) as follows. Let \(K_m\) be the clique added to \(C_n^\pm\) to obtain the clique extension \((C_n^\pm, A^\pm, K_m)\). Assign \(x_{v_i} = -1\) for \(i \in \left\{{0, \dots, n-1}\right\}\) and \(x_u = -(x_0 + x_{n-1})/m\) for every \(u \in V(K_m)\). We abuse notation and write \(x_i\) in place of \(x_{v_i}\) for \(i \in \left\{{0,\dots, n-1}\right\}\). The Rayleigh principle says that the smallest eigenvalue of \((C_n^\pm, A^\pm, K_m)\) is at most \[\frac{-2\sum_{i=0}^{n-2}x_ix_{i+1} + 2x_0x_{n-1} - 2(x_0 + x_{n-1})^2 + m(m-1)((x_0 + x_{n-1})/m)^2}{\sum_{i=0}^{n-1} x_i^2 + m((x_0 + x_{n-1})/m)^2},\] which is equal to \((-2n - 4/m)/(n + 4/m)\), and approaches \(-2\) as \(m \to \infty\). ◻

Proof. From 1([lem:n1], [lem:n2], [lem:p]) and 2, we obtain \(\ell, m \in \mathbb{N}^+\) such that \(P_\ell \not\in \mathcal{G}^\pm(\lambda)\), none of the following graphs \[\label{eqn:signed-k2-extensions} (\overline{K}_2, V(\overline{K}_2), 0, K_m), \dots, (\overline{K}_2, V(\overline{K}_2), \ell-1, K_m), \text{ and }(\overline{K}_2, V(\overline{K}_2), K_m)\tag{12}\] is in \(\mathcal{G}^\pm(\lambda)\), and \(\mathcal{X}(C, \ell, m) \cup \mathcal{X}(D, \ell, m)\) is disjoint from \(\mathcal{G}^\pm(\lambda)\). Since \(P_\ell \not\in \mathcal{G}^\pm(\lambda)\), no path extension in \(\mathcal{X}^\pm(C, \ell, m) \cup \mathcal{X}^\pm(D, \ell, m)\) is in \(\mathcal{G}^\pm(\lambda)\).

We are left to deal with the path-clique extensions and the clique extension \[\label{eqn:signed-extension} (F, A^\pm, 0, K_m), \dots, (F, A^\pm, \ell-1, K_m), \text{ and }(F, A^\pm, K_m),\tag{13}\] where \(F\) is \(C\) or \(D\), and \(A^\pm\) is the signed set of a nonempty vertex subset \(A\) of \(F\). We break the rest of the proof into three cases.

Case 1: \(A^\pm\) is all-positive or all-negative. This case follows since the signed graphs in 13 , after switching the cut-set between \(V(F)\) and its complement in case \(A^\pm\) is all-negative, become respectively \((F, A, 0, K_m), \dots, (F, A, \ell-1, K_m)\), and \((F, A, K_m)\) from the extension family \(\mathcal{X}(F, \ell, m)\), which is disjoint from \(\mathcal{G}^\pm(\lambda)\).

Case 2: There exists an edge \(uv\) of \(F\) such that \(\left\{{u^-, v^+}\right\} \subseteq A^\pm\). Since the all-negative triangle \(-K_3\), whose smallest eigenvalue is \(-2\), is switching equivalent to a subgraph of \((F, A^\pm, 0)\), no signed graph in 13 is in \(\mathcal{G}^\pm(\lambda)\).

Case 3: \(A^\pm\) is neither all-positive nor all-negative, and no edge \(uv\) of \(F\) satisfies that \(\left\{{u^-, v^+}\right\} \subseteq A^\pm\). Label the vertices of \(C\) and \(D\) as in 4. We may assume without loss of generality that \(\left\{{1^-, 3^+}\right\} \subseteq A^\pm\). One can check that, for \(F \in \left\{{C, D}\right\}\), the signed graphs in 12 , after switching at the vertex labeled by \(1\), are respectively subgraphs of those in 13 , and hence no signed graph in 13 is in \(\mathcal{G}^\pm(\lambda)\). ◻

Proof. Let \(G\) be the underlying graph of \(G^\pm\). One can check that \(G\) contains neither the claw graph nor the diamond graph as a subgraph. Thus 6 implies that \(G\) is a line graph of another graph, denoted \(H\), without isolated vertices. We may identify the vertex set of \(G^\pm\) with the edge set of \(H\).

For every \(v \in V(H)\), let \(E_v(H)\) be the set of edges that are incident to \(v\) in \(H\). Define a signing \(\sigma \colon \left\{{(v, e)}\colon{v \in V(H), e \in E_v(H)}\right\} \to \left\{{\pm 1}\right\}\) such that for every \(v \in V(H)\), \[\label{eqn:bidirected-graph} \sigma(v, e_1)\sigma(v, e_2) = A_{G^\pm}(e_1,e_2) \text{ for distinct } e_1, e_2 \in E_v(H).\tag{14}\] Such a signing \(\sigma\) can be chosen as follows: for every \(v\in V(H)\), define \(\sigma(v, e_0) = 1\) for some arbitrary \(e_0 \in E_v(H)\); and define \(\sigma(v, e) = A_{G^\pm}(e_0, e)\) for any other \(e \in E_v(H)\). Since \(G^\pm\) does not contain any subgraph that is switching equivalent to the all-negative triangle, it can be seen that 14 holds. Assigning \(\sigma(v, e)\) to every incidence \((v, e)\) of \(H\), we obtain a bidirected graph \(\vec{H}\) whose signed line graph is \(G^\pm\). ◻

Proof. Denote \(\mathcal{C}^\pm_n\) the set of signed cycles of length \(n\). We obtain \(\ell, m \in \mathbb{N}^+\) from 1 9 10 such that the following family \[\begin{align} \widetilde{\mathcal{F}}_1^\pm := & \left\{{S_4, P_\ell, -K_3}\right\} \cup \mathcal{X}^\pm(C, \ell, m) \cup \mathcal{X}^\pm(D, \ell, m) \\ & \cup \left\{{(C_n^\pm, V_2(C_n), \ell_0, K_m)}\colon{n \in \left\{{3, \dots, \ell + 1}\right\}, C_n^\pm \in \mathcal{C}_n^\pm, \ell_0 \in \left\{{0, \dots, \ell - 1}\right\}}\right\} \\ & \cup \left\{{(C_n^\pm, V_2(C_n), K_m)}\colon{n \in \left\{{3, \dots, \ell + 1}\right\}, C_n^\pm \in \mathcal{C}_n^\pm}\right\} \\ & \cup \left\{{(K_m, V(K_m), \ell_0, K_m)}\colon{\ell_0 \in \left\{{0, \dots, \ell-1}\right\}}\right\} \end{align}\] is disjoint from \(\mathcal{G}^\pm(\lambda)\). Let \(\mathcal{F}_1^\pm\) be the smallest family, that is closed under switching, containing \(\widetilde{\mathcal{F}}_1^\pm\). Clearly \(\mathcal{F}_1^\pm\) is also disjoint from \(\mathcal{G}^\pm(\lambda)\).

We omit the rest of the proof as it, mutatis mutandis, is very much like the one in the proof of 2 for \(\lambda< 2\) on . We point out that one should make use of 11 12 in place of 3 6 respectively. ◻

Proof of 3 for \(\lambda< 2\). Let \(N \in \mathbb{N}\) and \(\mathcal{F}_1^\pm\) be given by 13, and set \[\begin{align} \mathcal{F}_0^\pm & := \left\{{G^\pm \not\in \mathcal{G}^\pm(\lambda)}\colon{G^\pm \text{ has at most }N\text{ vertices}}\right\}, \\ \widetilde{\mathcal{F}}_2^\pm & := \left\{{G^\pm \not\in \mathcal{G}^\pm(\lambda)}\colon{\exists \vec{H} \in \vec{\mathcal{T}}_N \text{ s.t. }G^\pm \text{ is the signed line graph of }\vec{H}}\right\}, \end{align}\] where \(\vec{\mathcal{T}}_N\) is the family of bidirected rooted tree such that every connected component obtained from removing the root has at most \(N\) vertices. Setting \(\mathcal{F}_2^\pm\) to be the family of signed graphs that are minimal in \(\widetilde{\mathcal{F}}_2^\pm\) under taking subgraphs, one can check that \(\mathcal{F}_0^\pm \cup \mathcal{F}_1^\pm \cup \mathcal{F}_2^\pm\) is a forbidden subgraph characterization of \(\mathcal{G}^\pm(\lambda)\).

It suffices to prove that \(\mathcal{F}_2^\pm\) is finite. Let \(\vec{T}_1, \dots, \vec{T}_n\) be an enumeration of bidirected rooted trees \(\vec{T}\) on at most \(N+1\) vertices. We encode \(G^\pm \in \mathcal{F}_2^\pm\) by \(t_{G^\pm} \in \mathbb{N}^n\) as follows. Let \(\vec{H}\) be the bidirected rooted tree in \(\vec{\mathcal{T}}_N\) such that \(G^\pm\) is the signed line graph of \(\vec{H}\). After removing the root \(u\) from \(\vec{H}\), let \(U_1, U_2, \dots, U_m\) be the vertex sets of the connected components. For \(i \in \left\{{1, \dots, m}\right\}\), we view the subgraph \(\vec{H}_i := \vec{H}[\left\{{u}\right\} \cup U_i]\) as a bidirected tree rooted at \(u\). Set \(t_{G^\pm} = (t_1, \dots, t_n)\), where \(t_i\) is the number of occurrences of \(\vec{T}_i\) in \(\vec{H}_1, \dots, \vec{H}_m\). Because no member of \(\mathcal{F}_2^\pm\) is a subgraph of any other, one can deduce that \(\left\{{t_{G^\pm}}\colon{G^\pm \in \mathcal{F}_2^\pm}\right\}\) is an antichain in \((\mathbb{N}^n, \le)\), and so \(\mathcal{F}_2^\pm\) is finite by 5. ◻

Proof of 3 for \(\lambda\in [2, \lambda^*)\). Using the fact that every minimal forbidden subgraph for \(\mathcal{G}^\pm(2)\) has at most \(10\) vertices (see [23]), and 14, one can prove this case by following the argument in the proof of 2 for \(\lambda\in [2, \lambda^*)\) on . ◻

Proof of 14. Suppose that \(\lambda\in [2, \lambda^*)\). Let \(\mathcal{F}^\pm\) denote the set of minimal forbidden subgraphs for the family \(\mathcal{D}^\pm_\infty\). According to 15, the family \(\mathcal{F}^\pm\) is finite. Combining 14 15, we choose \(\ell, m \in \mathbb{N}^+\) such that for every \(F^\pm \in \mathcal{F}^\pm\), the signed extension family \(\mathcal{X}^\pm(F^\pm, \ell, m)\) is disjoint from \(\mathcal{G}^\pm(\lambda)\). We know that \(S_5 \not\in \mathcal{G}^\pm(\lambda)\) and \(-K_4 \not\in \mathcal{G}^\pm(\lambda)\). In particular, no graph in \(\mathcal{G}^\pm(\lambda)\) contains a subgraph that is switching equivalent to any member in the following family \[\label{eqn:main2-2} \left\{{S_5, -K_4}\right\} \cup \bigcup_{F^\pm \in \mathcal{F}^\pm} \mathcal{X}^\pm(F^\pm, \ell, m).\tag{15}\] Using 11, we obtain \(N \in \mathbb{N}\) such that for every connected signed graph \(G^\pm\) with more than \(N\) vertices, if no member in 15 is switching equivalent to a subgraph of \(G^\pm\), then neither is any \(F^\pm \in \mathcal{F}^\pm\), and so \(G^\pm\) is represented by a subset of \(D_n\) and is clearly in \(\mathcal{G}^\pm(2)\). This implies that every connected graph in \(\mathcal{G}^\pm(\lambda)\setminus \mathcal{G}^\pm(2)\) has at most \(N\) vertices. ◻

Proof of 3 for \(\lambda\ge \lambda^*\). If \(\mathcal{F}^\pm\) is a finite forbidden subgraph characterization of \(\mathcal{G}^\pm(\lambda)\), then the all-positive signed graphs in \(\mathcal{F}^\pm\) would form a finite forbidden subgraph characterization of \(\mathcal{G}(\lambda)\), which contradicts 2 for \(\lambda\ge \lambda^*\). ◻

Proof. According to 2, we can take a finite forbidden subgraph characterization, denoted \(\mathcal{H}\), of the family \(\mathcal{G}^\mp(\lambda)\) of signed graphs with largest eigenvalue at most \(\lambda\). Thus \(M_{p, \mathcal{H}}(\lambda, N)\) is the maximum possible value of \(\operatorname{mult}(\lambda, G^\pm)\) over all signed graphs \(G^\pm\) on at most \(N\) vertices that satisfy \(\chi(G^\pm) \le p\) and \(\lambda^1(G^\pm) \le \lambda\). Note that \(M_{p, \mathcal{H}}(\lambda, N)\) is a nondecreasing function of \(N\). We break the rest of the proof into two cases.

Case 1: \(M_{p, \mathcal{H}}(\lambda, N) = 0\) for every \(N \in \mathbb{N}^+\). In other words, there is no signed graph \(G^\pm\) that satisfy \(\chi(G^\pm) \le p\) and \(\lambda^1(G^\pm) = \lambda\). Thus this case corresponds to the case where \(k_p(\lambda)= \infty\). According to 17 18, we have \(N_{\alpha,\beta}(d)= d + O_{\alpha,\beta}(1)\).

Case 2: \(M_{p, \mathcal{H}}(\lambda, N) > 0\) for every \(N \ge d_0\). This case corresponds to the case where \(k_p(\lambda)< \infty\). Suppose that \(d \ge d_0\). 17 says that \(N_{\alpha,\beta}(d)\ge d\), and so \(M_{p, \mathcal{H}}(\lambda, N_{\alpha,\beta}(d)) > 0\). Let \(G^\pm\) be a signed graph with at most \(N_{\alpha,\beta}(d)\) vertices that satisfy \(\chi(G^\pm) \le p\), \(\lambda^1(G^\pm) \le \lambda\) and \(\operatorname{mult}(\lambda, G^\pm) = M_{p, \mathcal{H}}(\lambda, N_{\alpha,\beta}(d))\). Thus \[k_p(\lambda)\le \frac{\abs{G^\pm}}{\operatorname{mult}(\lambda, G^\pm)} \le \frac{N_{\alpha,\beta}(d)}{M_{p, \mathcal{H}}(\lambda, N_{\alpha,\beta}(d))}.\] 18 then implies that \[N_{\alpha,\beta}(d)\le \frac{k_p(\lambda)d}{k_p(\lambda)-1} + O_{\alpha,\beta}(1),\] which, in view of 16 17, gives \(N_{\alpha,\beta}(d)= k_p(\lambda)d / (k_p(\lambda)- 1) + O_{\alpha,\beta}(1)\). ◻

Proof of 16 for \(\lambda< 2\). We obtain \(\ell \in \mathbb{N}^+\) from 1([lem:p]) such that \(P_{\ell+1} \not\in \mathcal{G}^\pm(\lambda)\). Applying 11 to \(F^\pm = K_1\) (the \(1\)-vertex graph), \(k_1 = 4\), \(k_2 = 3\) and \(m = 2p\), we obtain \(N \in \mathbb{N}\) such that for every connected signed graph \(G^\pm\), if \(G^\pm\) does not contain any subgraph that is switching equivalent to any member in \(\left\{{S_4, -K_3}\right\} \cup \mathcal{X}^\pm(K_1, \ell, 2p)\), then \(G^\pm\) contains at most \(N\) vertices.

It suffices to show that for every connected signed graph \(G^\pm\) with more than \(N\) vertices, either \(\chi(-G^\pm) > p\) or \(G^\pm \not\in \mathcal{G}^\pm(\lambda)\). By our choice of \(N\), the signed graph \(G^\pm\) contains a subgraph that is switching equivalent to a member in \(\left\{{S_4, -K_3}\right\} \cup \mathcal{X}^\pm(K_1, \ell, 2p)\). We break the rest of the proof into two cases.

Case 1: \(G^\pm\) contains a subgraph that is switching equivalent to \(S_4\), \(-K_3\), or a path extension in \(\mathcal{X}^\pm(K_1, \ell, 2p)\). Since \(\lambda_1(S_4) = \lambda_1(-K_3) = -2\) and every path extension in \(\mathcal{X}^\pm(K_1, \ell, 2p)\) is switching equivalent to \(P_{\ell+1}\), the signed graph \(G^\pm\) is not in \(\mathcal{G}^\pm(\lambda)\).

Case 2: \(G^\pm\) contains a subgraph that is switching equivalent to a path-clique extension or a clique extension in \(\mathcal{X}^\pm(K_1, \ell, 2p)\). Observe that every path-clique extension and every clique extension in \(\mathcal{X}^\pm(K_1, \ell, 2p)\) contains a subgraph that is switching equivalent to \(K_{2p+1}\), and moreover every signed graph that is switching equivalent to \(K_{2p+1}\) always contains \(K_{p+1}\) as a subgraph. Thus the signed graph \(G^\pm\) contains \(K_{p+1}\) as a subgraph. Therefore \(-G^\pm\) contains \(-K_{p+1}\) as a subgraph, and so \(\chi(-G^\pm) \ge p+1\). ◻

Proof of 16 for \(\lambda\in (2, \lambda^*)\). 14 implies that there exists \(N\in\mathbb{N}\) such that every connected signed graph \(G^\pm\) with \(\lambda_1(G^\pm) = -\lambda\) has at most \(N\) vertices. ◻

Proof. Suppose that \(G^\pm\) is represented by \(V \subseteq D_n\). Construct a bidirected multigraph \(\vec{H}\) with vertices \(v_1, \dots, v_n\) and incidence signing \(\sigma\) as follows. For each vector in \(V\) of the form \(\varepsilon_1 \boldsymbol{e}_i + \varepsilon_2 \boldsymbol{e}_j\) with \(i < j\), we put an edge \(e\) connecting \(v_i\) and \(v_j\), and we assign \(\sigma(v_i, e) = \varepsilon_1\) and \(\sigma(v_j, e) = \varepsilon_2\). For every pair of parallel edges \(e_1\) and \(e_2\), which connect \(v_i\) and \(v_j\), since \(\sigma(v_i, e_1)\boldsymbol{e}_i + \sigma(v_j, e_1)\boldsymbol{e}_j\) and \(\sigma(v_i, e_2)\boldsymbol{e}_i + \sigma(v_j, e_2)\boldsymbol{e}_j\) are two distinct vectors from \(V\), their inner product satisfies \[\left\{{0, \pm 2}\right\} \ni \sigma(v_i, e_1)\sigma(v_i, e_2) + \sigma(v_j, e_1)\sigma(v_j, e_2) = A_{G^\pm}(e_1,e_2) \in \left\{{0,\pm 1}\right\},\] and so their inner product must be \(0\). Therefore \(\vec{H}\) is a bona fide bidirected multigraph. We may remove all the isolated vertices (if any) from \(\vec{H}\).

Conversely one can read off the vectors in \(V\) from \(\vec{H}\) — for every edge \(e\), include the associated vector \(\vec{e} \in D_n\) in \(V\). Furthermore one can reconstruct \(G^\pm\) from \(\vec{H}\) as follows. We identify the vertex set of \(G^\pm\) with the edge set of \(\vec{H}\), and for each pair of distinct vertices \(e_1\) and \(e_2\) of \(G^\pm\), they are adjacent in \(G^\pm\) if and only if \(e_1\) and \(e_2\) intersect at one vertex, say \(v\), in \(\vec{H}\), and the sign of the edge \(e_1e_2\) in \(G^\pm\) is \(\sigma(v, e_1)\sigma(v, e_2)\). One can then check that the reconstructed \(G^\pm\) is indeed represented by \(V\).

Finally, it is routine to transfer properties back and forth between \(G^\pm\) and \(\vec{H}\). ◻

Proof. According to 20, it suffices to show that for every connected bidirected multigraph \(\vec{H}\) with \(n\) vertices and \(m\) edges, if \(\vec{H}\) has a proper \(p\)-edge-coloring, then \[\frac{m}{m - \mathop{\mathrm{rank}}V} \ge \left(\frac{p}{p-1}\right)^2 \text{ or equivalently }\frac{m}{\mathop{\mathrm{rank}}V} \le \frac{p^2}{2p-1}, \quad\text{where } V := \left\{{\vec{e} \in D_n}\colon{e \in E(\vec{H})}\right\},\] and equality holds if and only if \(\vec{H}\) is the complete bipartite graph \(K_{p,p}\) with uniform vertices.

Suppose that \(c\colon E(\vec{H}) \to \left\{{c_1, \dots, c_p}\right\}\) is a proper \(p\)-edge-coloring of \(\vec{H}\). One can deduce from 15 the following properties.

1. For two edges \(e_1\) and \(e_2\) that intersect at a vertex \(v\), if \(\sigma(v, e_1) = \sigma(v, e_2)\), then \(c(e_1) \neq c(e_2)\).

2. For two edges \(e_1\) and \(e_2\) that intersect at a vertex \(v\), if \(\sigma(v, e_1) \neq \sigma(v, e_2)\), then \(c(e_1) = c(e_2)\), and any other edge incident to \(v\) has to be parallel to either \(e_1\) or \(e_2\).

We break the rest of the proof on the upper bound of \(m / \mathop{\mathrm{rank}}V\) into two cases.

Case 1: \(\vec{H}\) has no parallel edges. We claim that the maximum degree of \(\vec{H}\) is at most \(p\). Suppose on the contrary that \(k\) edges \(e_1, \dots, e_k\) pairwise intersect at a vertex \(v\), where \(k > p\). Because \(k > p \ge 3\), the contrapositive of [item:p-b] implies that \(\sigma(v, e_i)\) is the same for \(i \in \left\{{1, \dots, k}\right\}\). Moreover [item:p-a] says that \(c(e_1), \dots, c(e_k)\) are distinct, which contradicts the assumption that \(c\) is a proper \(p\)-edge-coloring. In particular, the claim implies that \[\label{eqn:kpl-m} m/n \le p/2.\tag{17}\]

Since \(\vec{H}\) is connected, one can check that the set of vectors \(\left\{{\vec{e} \in D_n}\colon{e \in E(T)}\right\}\), where \(T\) is a spanning tree of \(\vec{H}\), is linearly independent. Therefore \(\mathop{\mathrm{rank}}V \in \left\{{n - 1, n}\right\}\). We may assume that \[4 \le n \le 2p \quad\text{and}\quad \mathop{\mathrm{rank}}V = n-1.\] Indeed, in the case where \(n \le 3\), we have \[\frac{m}{\mathop{\mathrm{rank}}V} \le \frac{m}{n-1} \le \frac{\binom{n}{2}}{n-1} = \frac{n}{2} \le \frac{3}{2} < \frac{9}{5} \le \frac{p^2}{2p-1},\] in the case where \(n > 2p\), we have \[\frac{m}{\mathop{\mathrm{rank}}V} \le \frac{m}{n-1} \stackrel{\eqref{eqn:kpl-m}}{\le} \frac{p/2}{1-1/n} < \frac{p/2}{1-1/(2p)} = \frac{p^2}{2p-1}.\] and in the case where \(\mathop{\mathrm{rank}}V = n\), we also have \[\frac{m}{\mathop{\mathrm{rank}}V} = \frac{m}{n} \stackrel{\eqref{eqn:kpl-m}}{\le} \frac{p}{2} < \frac{p^2}{2p-1},\]

Let \(U\) be the vertex set of \(\vec{H}\), and define the vertex subset \[U_0 := \left\{{u \in U}\colon{u \text{ is \emph{not} uniform}}\right\}.\] We claim that \(\vec{H}[U \setminus U_0]\) is bipartite. To specify its bipartition, let \(\boldsymbol{x}\colon U \to \mathbb{R}\) be a nonzero vector in the orthogonal complement of \(V\). For every edge \(e\in E(\vec{H})\) with endpoints \(u_1\) and \(u_2\), since \(\boldsymbol{x}\) is orthogonal to the vector \(\vec{e}\) associated to \(e\), we know that \[\label{eqn:sigma-c} \sigma(u_1, e)\boldsymbol{x}(u_1) + \sigma(u_2, e)\boldsymbol{x}(u_2) = 0,\tag{18}\] hence \(\abs{\boldsymbol{x}(u_1)} = \abs{\boldsymbol{x}(u_2)}\). Because \(\vec{H}\) is connected, we deduce that \(\abs{\boldsymbol{x}(u)}\) is constant for every \(u \in U\), and in particular, \(\boldsymbol{x}(u) \neq 0\) for every \(u \in U\). Since every vertex in \(U \setminus U_0\) is uniform, we partition \(U \setminus U_0\) as follows: \[\begin{align} U_1 & := \left\{{u \in U \setminus U_0}\colon{\sigma(u, e)\boldsymbol{x}(u) > 0 \text{ for every edge }e \text{ incident to }u}\right\}, \\ U_2 & := \left\{{u \in U \setminus U_0}\colon{\sigma(u, e)\boldsymbol{x}(u) < 0 \text{ for every edge }e \text{ incident to }u}\right\}. \end{align}\] In view of 18 , we deduce that \(\vec{H}[U \setminus U_0]\) is a bipartite graph with parts \(U_1\) and \(U_2\), and so the number of edges in \(\vec{H}[U \setminus U_0]\) is at most \(\abs{U_1}\abs{U_2}\). According to [item:p-b], every vertex in \(U_0\) has degree at most \(2\). Thus, we can estimate \(m\) using \(n_0 := \abs{U_0}\) as follows: \[m \le \abs{U_1}\abs{U_2} + 2\abs{U_0} \le \left(\frac{n - n_0}{2}\right)^2 + 2n_0 \le \max\left(\frac{n^2}{4}, 2n-3\right),\] where the last inequality assumes that \(0 \le n_0 \le n-2\). In the corner case where \(n_0 \ge n-1\), we can estimate \(m\) by \[2m \le (n-1)(\abs{U_1} + \abs{U_2}) + 2\abs{U_0} = (n-1)(n - n_0) + 2n_0 \le 3(n-1),\] which implies \(m \le 3(n-1)/2 < 2n-3\). Therefore, we always have \[\frac{m}{\mathop{\mathrm{rank}}V} = \frac{m}{n-1} \le \max\left(\frac{n^2}{4(n-1)}, \frac{2n-3}{n-1}\right) = \begin{cases} \frac{2n-3}{n-1} & \text{if }n < 6, \\ \frac{n^2}{4(n-1)} & \text{if }n \ge 6, \end{cases}\] which, as a function of \(n\), increases on \((1,\infty)\). As \(n \le 2p\) and \(p \ge 3\), the function reaches its maximum \(p^2/(2p-1)\) at \(n = 2p\), and so \(m/\mathop{\mathrm{rank}}V \le p^2/(2p-1)\). It is easy to see that equality holds if and only if \(\vec{H}\) is the complete bipartite graph \(K_{p,p}\) with uniform vertices.

Case 2: \(\vec{H}\) has parallel edges. Let \(e_1\) and \(e_2\) be a pair of parallel edges. Since \(\vec{H}\) is connected, there is a spanning tree \(T\) that contains \(e_1\). One can check that the set of vectors \(\left\{{\vec{e} \in D_n}\colon{e \in E(T) \cup \left\{{e_2}\right\}}\right\}\) is linearly independent. Therefore \[\mathop{\mathrm{rank}}V = n.\]

We next use the discharging method to bound the average degree \(2m / n\) of \(\vec{H}\). Each vertex \(v\) starts with the charge \(d(v)\), that is, the degree of \(v\). We claim that for every vertex \(v\) with \(d(v) > p\), exactly one of the following two situations happens.

1. The vertex \(v\) is uniform, that is, the sign \(\sigma(v, e)\) is the same for every edge \(e\) incident to \(v\).

2. The edges incident to \(v\) are precisely two pairs \((e_1, e_1')\) and \((e_2, e_2')\) of parallel edges satisfying \(\sigma(v, e_1) \neq \sigma(v, e_2)\), and in particular \(d(v) = 4\) and \(p = 3\).

Indeed, suppose that \(d(v) > p\), and suppose that situation [item:p-1] does not happen, that is, there exist two edges \(e_1\) and \(e_2\) incident to \(v\) such that \(\sigma(v, e_1) \neq \sigma(v, e_2)\). Because \(d(v) > p \ge 3\), we may further assume that \(e_1\) and \(e_2\) intersect at \(v\) by replacing \(e_1\) or \(e_2\) with another edge incident to \(v\) in case \(e_1\) and \(e_2\) are parallel. Because \(d(v) \ge 4\), according to [item:p-b], situation [item:p-2] must happen.

To describe the discharging rules, we say that two edges \(e_1\) and \(e_2\) are twin if they are parallel and \(c(e_1) = c(e_2)\), and for every vertex \(v\) with \(d(v) > p\), we call \(v\) a type I vertex when [item:p-1] happens, and a type II vertex when [item:p-2] happens.

• The first discharging rule sends \(1\) from every type I vertex \(v\) to each of its neighbors \(v'\) that are connected to \(v\) through twin edges.

• The second discharging rule sends \(1/2\) from every type II vertex \(v\) to each of its two neighbors.

One can further deduce from 15 the following property of twin edges.

1. For twin edges \(e_1\) and \(e_2\) incident to a vertex \(v\), if \(\sigma(v, e_1) \neq \sigma(v, e_2)\), then \(e_1\) and \(e_2\) are the only two edges incident to \(v\).

We first consider the charge of each vertex after the first discharging rule is applied. Suppose that \(v\) is a type I vertex, and \(v'\) is an arbitrary vertex that is connected to \(v\) through a pair of parallel edges \(e_1\) and \(e_2\). Since \(\sigma(v, e_1) = \sigma(v, e_2)\), it must be the case that \(\sigma(v', e_1) \neq \sigma(v', e_2)\), and so \(v'\) is not a type I vertex. Thus \(v\) does not receive any charge from its neighbors. According to [item:p-a], among all the edges incident to \(v\), only the parallel ones can receive identical colors. Thus after \(v\) sends out charges to its neighbors, its charge decreases exactly to the number of distinct colors assigned to the edges incident to \(v\), and so the charge of \(v\) is at most \(p\) now. Suppose in addition that \(e_1\) and \(e_2\) are twin edges, or in other words, \(v'\) receives \(1\) from \(v\). According to [item:p-c], the only edges incident to \(v'\) are \(e_1\) and \(e_2\), and so the charge of \(v'\) is at most \(3\), which is at most \(p\), now.

We then consider the charge of each vertex after the second discharging rule is applied. Notice that the second discharging rule only kicks in when \(p = 3\). Suppose that \(v\) is a type II vertex, and two pairs \((e_1, e_1')\) and \((e_2, e_2')\) of parallel edges connect \(v\) respectively to \(v_1\) and \(v_2\) such that \(\sigma(v, e_1) \neq \sigma(v, e_2)\). Without loss of generality, we may assume that \(\sigma(v, e_1) = +1\) and \(\sigma(v, e_2) = -1\). We have the four possibilities for \(\sigma(v, e_1')\) and \(\sigma(v, e_2')\). Once \(\sigma(v, e_1')\) and \(\sigma(v, e_2')\) are chosen, we can determine, according to [item:p-a] and [item:p-b], which edges incident to \(v\) receive identical or distinct colors. We summarize the four possibilities in the following figure. For each possibility, it is easy to check that \(v\) did not receive any charge from \(v_1\) or \(v_2\) when the first discharging rule was applied. Therefore the final charge of \(v\) is \(3\), which is equal to \(p\).

We are left to decide the final charge of \(v_1\) and \(v_2\). Observe that for \(i \in \left\{{1,2}\right\}\) there are, au fond, only three possible ways, as shown below, to color \(e_i\) and \(e_i'\) and to assign \(\sigma(v_i, e_i)\) and \(\sigma(v_i, e_i')\). For the first possibility, according to [item:p-c], the only edges incident to \(v_i\) are \(e_i\) and \(e_i'\), and so the final charge of \(v_i\) is \(5/2\), which is less than \(p\). For the other two possibilities, the contrapositive of [item:p-b] implies that \(v_i\) must be uniform, and so its charge was at most \(p\) after the first discharging rule was applied. Assume for the sake of contradiction that \(v_i\) is connected to another type II vertex \(w\) through edges \(f_i\) and \(f_i'\). Since \(v_i\) is uniform, in view of the three possibilities above, we know that \(c(e_i) \neq c(e_i')\) and \(c(f_i) \neq c(f_i')\). In view of [item:p-a], we know that \(\left\{{c(e_i), c(e_i')}\right\} \cap \left\{{c(f_i), c(f_i')}\right\} = \varnothing\). Thus the four edges \(e_i\), \(e_i'\), \(f_i\) and \(f_i'\) receive distinct colors under \(c\), which contradicts the assumption that \(p = 3\). Therefore \(v\) is the only type II neighbor of \(v_i\), and the final charge of \(v_i\) is at most \(p + 1/2\).

Since the discharging rules preserve the total charge, the average degree \(2m/n\) is at most the maximum final charge, which is at most \(p + 1/2\). Finally, we obtain that \[\frac{m}{\mathop{\mathrm{rank}}V} = \frac{m}{n} \le \frac{p+1/2}{2} < \frac{p^2}{2p-1}. \qedhere\] ◻

Proof of 16 for \(\lambda= 2\). From 19 and 16, we know that \(k_p(2)\) is the smaller of the two quantities \(p^2/(p-1)^2\) and \[k_p^* := \inf\left\{{\frac{\abs{G^\pm}}{\operatorname{mult}(-2, G^\pm)}}\colon{G^\pm \text{ is represented by a subset of }E_8 \text{ and } \chi(-G^\pm) \le p}\right\}.\] Because there are only finitely many signed graphs that are represented by a subset of \(E_8\), the infimum in the definition of \(k_p^*\) is in fact a minimum, hence \(k_p(2)\) is achievable. Moreover \(k_p^* \ge k^*\), where \[\label{eqn:k-star} k^* := \min\left\{{\frac{\abs{G^\pm}}{\operatorname{mult}(-2, G^\pm)}}\colon{G^\pm \text{ is represented by a subset of }E_8}\right\}.\tag{19}\] Since \(k^* > 1\), there exists \(p_0 \ge 3\) such that \(p^2 / (p-1)^2 \le k^* \le k_p^*\) for every \(p \ge p_0\). ◻