Classification of equiangular lines with fixed angle arccos ⁡ ( 1 / ( 1 + 2 ​ 2 ) ) \arccos(1/(1+2\sqrt{2})) Theodore Gossett, Zilin Jiang Adam Teets, Zoe Wellner Abstract We determine the maximum number N α ​ ( d ) N_{\alpha}(d) of equiangular lines with fixed angle arccos ⁡ α \arccos\alpha for α = 1 / ( 1 + 2 ​ 2 ) \alpha=1/(1+2\sqrt{2}) in d d -dimensional Euclidean space: 2 , 3 , 4 , 6 , 8 , 10 , 14 , 15 , 16 , 17 , 18 , 20 , 22 2,3,4,6,8,10,14,15,16,17,18,20,22 for d ∈ { 2 , … , 14 } d\in\{2,\dots,14\} , and max ⁡ ( 24 , ⌊ 3 ​ ( d − 1 ) / 2 ⌋ ) \max(24,\lfloor 3(d-1)/2\rfloor) for d ≥ 15 d\geq 15 . This appears to be the first complete determination of N α ​ ( d ) N_{\alpha}(d) in all dimensions d d for a fixed nontrivial α \alpha , since the work of Lemmens and Seidel for α = 1 / 3 \alpha=1/3 in 1973. 1 Introduction A set of lines passing through the origin in d -dimensional Euclidean space \mathbb{R}^{d} is called equiangular if any two of them form the same angle. The problem of determining the maximum cardinality N(d) of an equiangular line system in \mathbb{R}^{d} , formally posed by van Lint and Seidel [ 20 ] in 1966, is considered to be one of the foundational problems of algebraic graph theory. The exact value of N(d) has been determined for only finitely many d . After decades of research, the state of the art for d\leq 43 is summarized as follows. d 2 3–4 5 6 7–14 15 16 17 18 19 20 21 22 23–41 42 43 N(d) 3 6 10 16 28 36 40 48 57–59 72–74 90–94 126 176 276 276–288 344 This table has a long history. In 1948, Haantjes [ 14 ] determined N(3)=6 and N(4)=6 — the optimal configuration in \mathbb{R}^{3} is given by the 6 diagonals of a regular icosahedron. Later, van Lint and Seidel [ 20 ] determined N(d) for d\in\left\{{5,6,7}\right\} . Lemmens and Seidel [ 17 ] determined N(d) for d\in\left\{{15,21,22,23}\right\} , and they mentioned in their work Asche’s and Taylor’s construction implying that N(19)\geq 72 and N(20)\geq 90 . Progress has been stalled for more than forty years. Greaves, Koolen, Munemasa, and Szöllősi [ 9 ] improved two long-standing upper bounds on N(14) and N(16) , and Barg and Yu [ 3 ] determined N(d)=276 for every d\in\left\{{24,\dots,41}\right\} and N(43)=344 , while leaving open the problem of N(42) , with 276\leq N(42)\leq 288 . Research on N(d) has remained active in recent years: Greaves and Yatsyna [ 13 ] improved the upper bound N(17)\leq 49 ; Greaves, Syatriadi and Yatsyna in two subsequent works [ 11 , 12 ] determined N(14)=28 , N(16)=40 , and N(17)=48 , and they also improved the bounds to N(18)\geq 57 , N(19)\leq 74 and N(20)\leq 94 ; and most recently, Greaves and Syatriadi [ 10 ] improved the upper bound N(18)\leq 59 . The question of determining the maximum number N_{\alpha}(d) of equiangular lines in \mathbb{R}^{d} with common angle \arccos\alpha was first raised by Lemmens and Seidel [ 17 ] in 1973, who determined that N_{1/3}(d) equals 2,4,6,10,16 for d\in\left\{{2,\dots,6}\right\} , and \max(28,2(d-1)) for d\geq 7 . They also conjectured that N_{1/5}(d)=\max(276,\lfloor 3(d-1)/2\rfloor) for d\geq 23 , which was recently resolved by Cao, Koolen, Lin and Yu [ 5 ] . When 2\leq d\leq 22 , here are the known results. d 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 N_{1/5}(d) 2 3 4 6 7 9 10 12 16 18 20 26 28 36 40 48 57–59 72–74 90–94 126 176 In the above table, Greaves, Koolen, Munemasa, and Szöllősi [ 9 ] determined N_{1/5}(d) for d\in\left\{{2,\dots,11}\right\}\cup\left\{{13}\right\} , and Szöllősi and Östergård [ 19 ] determined it for d=12 . It is not a coincidence that the known results on N(d) and N_{1/5}(d) agree for d\in\left\{{14,\dots,41}\right\} — it follows from [ 17 , Theorem 3.7] asserting that N(d)\leq\max(N_{1/3}(d),N_{1/5}(d),\lfloor 48d/(49-d)\rfloor) for d\leq 48 . Recent work [ 4 , 2 , 15 ] culminated in a solution [ 16 ] of Jiang, Tidor, Yao, Zhang and Zhao to the problem of determining N_{\alpha}(d) in high dimensions. In particular, they proved for every integer k\geq 2 and d sufficiently large that N_{\alpha^{*}}(d)=\lfloor 3(d-1)/2\rfloor\text{ and }N_{1/(2k-1)}(d)=\lfloor kd/(k-1)\rfloor. Here and throughout, we fix the constant \alpha^{*}=\frac{1}{1+2\sqrt{2}}. We refer the reader to the excellent survey [ 22 ] of Zhao for the precise statement of the relevant result of [ 16 ] and the connection to graph eigenvalue multiplicity. Given that \alpha^{*} sits between 1/3 and 1/5 , one might hope to determine N_{\alpha^{*}}(d) for all dimensions d before tackling N_{1/5}(d) . Indeed, we resolve this problem. Theorem 1.1 . The maximum number of equiangular lines with fixed angle \arccos(\alpha^{*}) in d -dimensional Euclidean space satisfies N_{\alpha^{*}}(d)=\begin{cases}2,3,4,6,8,10,14,15,16,17,18,20,22&\text{for }d\in\left\{{2,\dots,14}\right\},\\ \max(24,\lfloor 3(d-1)/2\rfloor)&\text{for }d\geq 15.\end{cases} We prove the main theorem in the strongest possible sense — we classify equiangular line systems with fixed angle \arccos(\alpha^{*}) in \mathbb{R}^{d} , for all d , up to orthogonal transformations. To state our classification theorem, we recall the connection between equiangular lines, graphs and their Seidel matrices. The Seidel matrix of a graph G , denoted S(G) , is defined as J-I-2A(G) , where A(G) is the adjacency matrix of G , and the smallest Seidel eigenvalue of G is the smallest eigenvalue of S(G) . It was observed by van Lint and Seidel [ 20 ] that classifying equiangular line systems with fixed angle \arccos\alpha up to orthogonal transformations is equivalent to classifying graphs with smallest Seidel eigenvalue at least -1/\alpha up to switching equivalence (cf. [ 8 , Chapter 11] ). Definition 1.2 (Switching equivalence) . Given a graph G and a subset U\subseteq V(G) , the switching of G with respect to U , denoted G^{U} , is the graph obtained from G by toggling adjacency between every vertex in U and every vertex in V(G)\setminus U . Two graphs G and H are switching equivalent if there exists U\subseteq V(G) such that H is isomorphic to G^{U} . To describe most of the graphs with smallest Seidel eigenvalue at least -1/\alpha^{*} , we introduce the following notion. All subgraphs are induced throughout this paper. Definition 1.3 (Switching closure) . Given a family \mathcal{G} of graphs, the switching closure , denoted \langle\mathcal{G}\rangle_{\pm} , is the smallest class of graphs containing every member of \mathcal{G} that is closed under taking subgraphs, vertex-disjoint union, and switching equivalence. In Section 2 , we note the simple fact that every graph in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} has smallest Seidel eigenvalue at least -1/\alpha^{*} , where denotes the cherry graph (the path of length 3 ) throughout. We enumerate all other graphs with smallest Seidel eigenvalue at least -1/\alpha^{*} , and summarize the results as follows. Theorem 1.4 . Up to switching equivalence, there are a total of 63673 graphs outside \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} with smallest Seidel eigenvalue at least -1/\alpha^{*} with the following statistics, where the rank refers to the rank of S(G)+I/\alpha^{*} for a graph G . d 5 6 7 8 9 10 11 12 13 14 # 1 6 25 82 294 1047 3533 8929 14921 15799 minimum rank 5 6 6 6 7 7 8 8 8 8 15 16 17 18 19 20 21 22 23 24 25 26 27 28 10555 5030 2034 831 325 140 63 31 13 6 3 2 2 1 9 10 11 12 13 13 14 14 15 15 25 26 27 28 Moreover, up to switching equivalence, the graph achieving the minimum rank is unique for n\in\left\{{5,7,8,13,14,22,24,28}\right\} , and when n\in\left\{{5,8,14,28}\right\} , the unique graph is switching equivalent to the cycle graph C_{5} , the cycle graph C_{8} , the Heawood graph (see Figure 1 ) and the complement of the line graph of the complete graph K_{8} , respectively. Figure 1: Heawood graph. The rest of the paper is organized as follows. In Section 2 , we prove the main theorem assuming Theorem 1.4 . In Section 3 , we identify five graphs such that every graph outside \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} contains at least one of them as a subgraph. In Section 4 , we prove Theorem 1.4 by extending these five graphs. We conclude with a discussion of equiangular lines with fixed angle \arccos(1/3) and an open problem in Section 5 . Parts of our proofs are computer-assisted, using validated arithmetic. We describe each such proof in detail so that it can be independently reproduced. To help readers identify computer-assisted proofs, we use a bespoke symbol at the conclusion of each such proof. All our code, written in C++, is available as ancillary files in the arXiv version of this paper. We deliberately avoid third-party libraries, making it straightforward to adapt the code to other programming languages. 2 Proof of main theorem To establish the main theorem Theorem 1.1 assuming Theorem 1.4 , we first formally state the graph-theoretic characterization of equiangular line systems. Theorem 2.1 (van Lint and Seidel [ 20 ] ) . There is a one-to-one correspondence between systems of n equiangular lines with fixed angle \alpha in \mathbb{R}^{d} modulo orthogonal transformations and graphs of order n with smallest Seidel eigenvalue at least -1/\alpha and the multiplicity of -1/\alpha as a Seidel eigenvalue at least n-d modulo switching equivalence. ∎ Under the correspondence, there are two kinds of equiangular line systems: those that arise from graphs in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} and those from graphs not in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} . The next proposition deals with the former case, whereas Theorem 1.4 deals with the latter case. To this end, we need the following notion. Definition 2.2 (Closure) . Given a family \mathcal{G} of graphs, the closure , denoted \langle\mathcal{G}\rangle , of \mathcal{G} is the smallest class of graphs containing \mathcal{G} that is closed under taking subgraphs and vertex-disjoint union. Proposition 2.3 . Every graph in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} has smallest Seidel eigenvalue at least -1/\alpha^{*} . Moreover, for every d\in\mathbb{N}^{+} , the maximum order of a graph G in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} , for which the rank of S(G)+I/\alpha^{*} is at most d , is exactly \max(d,\lfloor 3(d-1)/2\rfloor) . The proof closely follows the proof of Theorem 1.2 and Proposition 3.2 in [ 16 ] . Proof. Let G be a graph in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} . Since switching equivalence preserves the eigenvalues of Seidel matrices, without loss of generality, we may assume that G is in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle , that is, each connected component of G is an isolated vertex, a single edge, or a cherry. Since the largest eigenvalue of is \sqrt{2} , every connected component of G has largest eigenvalue at most \sqrt{2} , and so does G itself. Thus S(G)+I/\alpha^{*}=J-I-2A(G)+I/\alpha^{*}=J+2\left(\sqrt{2}I-A(G)\right), (1) which is positive semidefinite. Therefore, the smallest Seidel eigenvalue of G is at least -1/\alpha^{*} . Now, suppose further that the rank of S(G)+I/\alpha^{*} is at most d . Let c be the number of cherries in G . If c=0 , then the largest eigenvalue of G is at most 1 , and so according to ( 1 ), the matrix S(G)+I/\alpha^{*} is positive definite, which implies that the rank of S(G)+I/\alpha^{*} is exactly d . Finally, we consider the case where c>0 . Since both J and \sqrt{2}I-A(G) are positive semidefinite, \ker\left(J+2\left(\sqrt{2}I-A(G)\right)\right)=\ker(J)\cap\ker\left(\sqrt{2}I-A(G)\right). By the Perron–Frobenius theorem, there is an eigenvector of A(G) associated with \sqrt{2} that has nonnegative entries. This vector lies in \ker(\sqrt{2}I-A(G)) , but not in \ker(J) , implying that \dim\ker\left(J+2\left(\sqrt{2}I-A(G)\right)\right)\leq\dim\ker(\sqrt{2}I-A(G))-1 . By the rank-nullity theorem, we obtain n-c=\rank(\sqrt{2}I-A(G))\leq\rank(J+2\left(\sqrt{2}I-A(G)\right))\leq d-1. Since c\leq n/3 , we have n\leq\lfloor 3(d-1)/2\rfloor . Moreover, when G is the vertex-disjoint union of \lfloor(d-1)/2\rfloor cherries along with (d-1)-2\lfloor(d-1)/2\rfloor isolated vertices, the order of G is exactly \lfloor 3(d-1)/2\rfloor , and the rank of \sqrt{2}I-A(G) is exactly d-1 , which implies that the rank of S(G)+I/\alpha^{*} is at most d via ( 1 ). ∎ Proof of Theorem 1.1 assuming Theorem 1.4 . By Theorem 2.1 , for each dimension d , we seek the largest order N_{\alpha^{*}}(d) of a graph G with smallest Seidel eigenvalue at least -1/\alpha^{*} such that the rank of S(G)+I/\alpha^{*} is at most d . If G is a graph in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} , then by Proposition 2.3 , the largest order of G is exactly \max(d,\lfloor 3(d-1)/2\rfloor) . Suppose that G is not in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} . According to Theorem 1.4 , the largest order of such a graph G with rank of S(G)+I/\alpha^{*} at most d is listed as follows. d 5 6 7 8 9 10 11 12 13 14 15–24 25 26 27 28– \infty maximum order 5 8 10 14 15 16 17 18 20 22 24 25 26 27 28 Taking the maximum of the two cases, we obtain the values of N_{\alpha^{*}}(d) for all d\in\mathbb{N}^{+} . ∎ 3 Minimal forbidden subgraphs To identify graphs such that every graph outside \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} contains at least one of them as a subgraph, we take the most economical approach. Definition 3.1 (Minimal forbidden subgraph) . Given a class \mathcal{C} of graphs that is closed under taking subgraphs, a graph F is a minimal forbidden subgraph for \mathcal{C} if F itself is not in \mathcal{C} , but every proper subgraph of F is in \mathcal{C} . To enumerate the minimal forbidden subgraphs for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} , we show that a large graph in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} is uniquely represented by a graph in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle under switching equivalence, and then characterize the minimal forbidden subgraphs for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle . Proposition 3.2 . For every G\in\langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle of order at least 7 , and every U\subseteq V(G) , if the switching G^{U} of G with respect to U is also in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle , then U is trivial, that is, U=\varnothing or U=V(G) . Proof. Suppose that G is a graph in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle of order n\geq 7 , and U\subseteq V(G) such that G^{U} is also in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle . We may assume that \lvert U\rvert\leq n/2 by taking the complement of U if necessary. Assume for the sake of contradiction that U\neq\varnothing . Set W=V(G)\setminus U . Clearly \lvert W\rvert\geq 4 . For every vertex u\in U , it has at least \lvert W\setminus N_{G}(u)\rvert neighbors inside W in G^{U} , where N_{G}(u) denotes the set of neighbors of u in G . Since G^{U}\in\langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle , its maximum degree is at most 2 , and so \lvert W\setminus N_{G}(u)\rvert\leq 2 . It must be the case that \lvert W\rvert=4 , \lvert N_{G}(u)\rvert=2 , and N_{G}(u)\subseteq W for every u\in U . Since G[\left\{{u}\right\}\cup N_{G}(u)] has to be a connected component of G that is isomorphic to for every u\in U , we have 2\lvert U\rvert\leq\lvert W\rvert=4 , which contradicts n\geq 7 . ∎ Proposition 3.3 . Any minimal forbidden subgraph for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle has at most 4 vertices. Proof. Suppose that G is a minimal forbidden subgraph for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle . Since G\notin\langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle but every proper subgraph of G is in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle , it must be the case that G is connected. There exists a vertex v of G such that G-v is still connected. Since G-v is a subgraph of , the graph G has at most 4 vertices. ∎ We bound the order of minimal forbidden subgraphs for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} in preparation for their enumeration. Lemma 3.4 . Any minimal forbidden subgraph for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} has at most 8 vertices. Proof. Let G be a minimal forbidden subgraph for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} on n vertices. Assume for the sake of contradiction that n\geq 9 . Fix a vertex v of G . Minimality means G-v is in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} . By applying a switching to G , we may assume that G-v is in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle , and that v has degree at most n/2 . We claim that G-u is in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle for every u\in V(G) . Take an arbitrary u\in V(G) . We may assume that u\neq v . Since G-u\in\langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} , there exists U\subseteq V(G)\setminus\left\{{u}\right\} such that (G-u)^{U}\in\langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle . We may assume that v\not\in U by taking the complement of U as a subset of V(G)\setminus\left\{{u}\right\} in case v\in U . Since G-v\in\langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle , clearly G-\left\{{u,v}\right\} is in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle . Since (G-\left\{{u,v}\right\})^{U} is also in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle , by Proposition 3.2 , we have that U is trivial as a subset of V(G)\setminus\left\{{u,v}\right\} . Suppose for a moment that U=V(G)\setminus\left\{{u,v}\right\} . Since the degree of v in (G-u)^{\left\{{v}\right\}} is at least n/2-1 , the graph (G-u)^{\left\{{v}\right\}}\not\in\langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle , which contradicts the fact that (G-u)^{\left\{{v}\right\}}=(G-u)^{U}\in\langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle . Therefore U=\varnothing , and G-u=(G-u)^{U}\in\langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle . Based on the claim, we observe that G is a minimal forbidden subgraph for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle on at least 9 vertices, which contradicts Proposition 3.3 . ∎ Our enumeration of minimal forbidden subgraphs for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} is a straightforward brute force approach. Lemma 3.5 . Up to switching equivalence, there are 5 minimal forbidden subgraphs for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} listed in Figure 2 . Figure 2: Minimal forbidden subgraphs for the switching closure of the cherry graph. Proof. By Lemma 3.4 , the order of any minimal forbidden subgraph for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} is at most 8 . To enumerate minimal forbidden subgraphs G for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} up to switching equivalence, we may assume that G on n vertices can be obtained from a graph in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle on n-1 vertices by adding a new vertex and specifying its neighbors among the n-1 existing vertices. Our algorithm first stores all graphs in \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle on up to 8 vertices in base up to switching equivalence, and then for graphs in base on up to 7 vertices, we add a new vertex, exhaust all possible vertex subsets as its neighborhood, and check whether each new graph G is a minimal forbidden subgraph for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} — G should not be switching equivalent to any of the graphs in base , but G-v should be switching equivalent to some graph in base for every vertex v of G . Finally, we add each such minimal forbidden subgraph to dict , provided it is not switching equivalent to any existing member of dict . Our code is available as min_forb.cpp , an auxiliary file in the arXiv version of the paper. ∎ For the rest of this section, we provide further details of our implementation. 3.1 Hash function of graphs and Seidel degrees A common routine in the above algorithm is to decide whether a graph G is switching equivalent to any graph in a given set of graphs. A brute force implementation would still run within a reasonable time limit. Nevertheless, we carry out the more efficient implementation since the code will be reused in Section 4 . Suppose that we need to check whether a graph G is switching equivalent to any existing member of set . To efficiently detect switching equivalence, we maintain a hash table hash of existing members of set using the following hash function. Definition 3.6 . Given a graph G , its vertex v , and k\in\mathbb{N} , the k -th Seidel degree of v in G is the (v,v) -entry of the k -th power of the Seidel matrix of G . Proposition 3.7 . For every graph G , every vertex subset U of G , every vertex v of G , and every k\in\mathbb{N} , the k -th Seidel degree of v in G is equal to that of v in G^{U} . Proof. Define D(U) to be the diagonal matrix on V(G) by D_{v,v}=1 if v\in U and D_{v,v}=-1 otherwise. The Seidel matrices of G and G^{U} are related by S(G^{U})=D(U)S(G)D(U) . Finally, since D(U)^{2}=I , we have S(G^{U})^{k}=D(U)S(G)^{k}D(U) , whose diagonal entries agree with those in S(G)^{k} . ∎ For a graph G of order n , its hash value is the sorted sequence of third Seidel degrees. We skip first and second Seidel degrees because they are always 0 and n-1 , respectively. Clearly, when two graphs are switching equivalent, their hash values are equal by Proposition 3.7 . This allows us to test whether G is switching equivalent to any existing member of set by examining only the members of hash[hv] , where hv is the hash value of G . In addition, when we search for a vertex subset U of G and an isomorphism between G^{U} and a member G^{\prime} of hash[hv] , we only map a vertex of G to a vertex of G^{\prime} that has the same third Seidel degree. 4 Enumeration of exceptional graphs In this section, we prove Theorem 1.4 by extending the minimal forbidden subgraphs for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} in Figure 2 to graphs with smallest Seidel eigenvalue at least -1/\alpha^{*} . Proof of Theorem 1.4 . To enumerate the graphs G\notin\langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} with smallest Seidel eigenvalue at least -1/\alpha^{*} up to switching equivalence, we generate these graphs in dict based on their order. At the start, dict[5] , dict[6] , dict[7] consist of those minimal forbidden subgraphs for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} in Figure 2 on 5,6,7 vertices whose smallest Seidel eigenvalue is at least -1/\alpha^{*} , and the counter n is set to 5 . It turns out that the smallest Seidel eigenvalue of the second graph in Figure 2 is less than -1/\alpha^{*} , and so we skip it. Whenever dict[n] is nonempty, we iterate through members of dict[n] before incrementing the counter n by 1 . For each G in dict[n] , we carry out the following steps. (i) We compute \rank(S(G)+I/\alpha^{*}) and record the current minimum rank in min_rank . (ii) We connect a new vertex to a vertex subset U of G in every possible way to obtain new graphs H . See Section 4.1 for a more efficient implementation. (iii) We store those graphs H that satisfy S(H)+I/\alpha^{*}\succeq 0 in a temporary array candidates . (iv) We merge candidates into dict[n+1] (cf. Section 3.1 ). Our program terminates at n=29 because dict[29] is empty. We also output the graphs achieving the minimum rank for each n\in\left\{{5,\dots,28}\right\} , and write all the graphs in dict[n] together with their rank to the file cherry-.txt . Our code is available as the ancillary file enum.cpp in the arXiv version of the paper. Based on the output, we observe that the graph achieving the minimum rank is unique for n\in\left\{{5,7,8,13,14,22,24,28}\right\} . When n\in\left\{{5,8,14,28}\right\} , the unique graph is switching equivalent to the cycle graph C_{5} , the cycle graph C_{8} , the Heawood graph and the complement of the line graph of the complete graph K_{8} , respectively, whereas when n\in\left\{{7,13,22,24}\right\} , the unique graph is not switching equivalent to any regular graph. ∎ Remark . Although no regular graph is switching equivalent to the unique graph (with smallest Seidel eigenvalue at least -1/\alpha^{*} ) achieving the minimum rank for each n\in\left\{{7,13,22,24}\right\} , one can still seek an easy-to-describe switching of these graphs. For example, when n=24 , the unique graph is switching equivalent to the following: take the Heawood graph in Figure 1 with bipartition A and B ; add four vertices c_{1},c_{2},c_{3},c_{4} , each connected to all vertices in B ; then add six more vertices, each connected to a distinct pair of vertices in \left\{{c_{1},c_{2},c_{3},c_{4}}\right\} . Remark . On a Mac mini equipped with an Apple M4 chip and 16 GB of memory, the program terminated in under 3 minutes. 4.1 Adding a new vertex To accelerate the generation of graphs, we leverage the computation done for G in dict[n] based on the following observation. Suppose that G is a graph such that S(G)+I/\alpha^{*}\succeq 0 . For U\subseteq V(G) , denote by G_{U}^{+} the graph obtained from G by connecting a new vertex to vertices in U . Set \mathcal{U}=\left\{{U\subseteq V(G)}\colon{S(G_{U}^{+})+I/\alpha^{*}\succeq 0}\right\}. For every W\subseteq V(H) , where H=G_{U}^{+} for some U\subseteq V(G) , note that S(H^{+}_{W})+I/\alpha^{*}\succeq 0 implies that S(G^{+}_{W\cap V(G)})+I/\alpha^{*}\succeq 0 , which is equivalent to W\cap V(G)\in\mathcal{U} . In other words, when we connect a new vertex to a vertex subset W of H , we need only consider W satisfying W\cap V(G)\in\mathcal{U} . To keep track of the set \mathcal{U} defined for G , we add an attribute possible_subsets , a list of distinct vertex subsets of G , to each graph G . For the minimal forbidden subgraphs for \langle\hbox to8.94pt{\vbox to8.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.62271pt\lower-1.62271pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 L 3.94 6.82 L 7.87 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 0 M 1.97 0 C 1.97 1.09 1.09 1.97 0 1.97 C -1.09 1.97 -1.97 1.09 -1.97 0 C -1.97 -1.09 -1.09 -1.97 0 -1.97 C 1.09 -1.97 1.97 -1.09 1.97 0 Z M 0 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 3.94 6.82 M 5.91 6.82 C 5.91 7.91 5.02 8.79 3.94 8.79 C 2.85 8.79 1.97 7.91 1.97 6.82 C 1.97 5.73 2.85 4.85 3.94 4.85 C 5.02 4.85 5.91 5.73 5.91 6.82 Z M 3.94 6.82}{} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.25,0.25,0.25}\lxSVG@begingroup@{fill} {}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 0 M 9.84 0 C 9.84 1.09 8.96 1.97 7.87 1.97 C 6.79 1.97 5.91 1.09 5.91 0 C 5.91 -1.09 6.79 -1.97 7.87 -1.97 C 8.96 -1.97 9.84 -1.09 9.84 0 Z M 7.87 0}{} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\rangle_{\pm} in Figure 2 , its possible_subsets consists of all the nonempty vertex subsets. For each G in dict[n] , instead of connecting a new vertex, say v , to a vertex subset U of G in every possible way, we connect v to S for every S in possible_subsets of G . To obtain possible_subsets of the graphs obtained from G , we initially set new_possible_subsets to be the empty list. For each U in possible_subsets of G , check whether S(G_{U}^{+})+I/\alpha^{*}\succeq 0 , and if so, we append both U and U\cup\left\{{v}\right\} to new_possible_subsets , and we append G_{U}^{+} to candidates . Finally, we set possible_subsets of each graph G^{\prime} in candidates to new_possible_subsets . Remark . The same idea of carrying computation forward previously appeared in [ 1 ] , where Acharya and Jiang classified connected graphs G satisfying A(G)+\lambda^{*}I\succeq 0 , where \lambda^{*}\approx 2.01980 . 4.2 Positive semidefiniteness and rank Testing whether S(G)+I/\alpha^{*}\succeq 0 amounts to verifying that all the roots of p_{G}(x-1/\alpha^{*}) are non-negative, where p_{G} is the characteristic polynomial of S(G) . We recall the following criterion, which is a special case of Descartes’ rule of signs: for x_{1},\dots,x_{n}\in\mathbb{R} , they are non-negative if and only if their elementary symmetric functions are all non-negative. Suppose that p_{G}\left(x-1/\alpha^{*}\right)=c_{n}x^{n}+\dots+c_{0}. We can conclude that S(G)+I/\alpha^{*}\succeq 0 if and only if (-1)^{n-k}c_{k}\geq 0 for every k\in\left\{{0,\dots,n}\right\} . To compute the characteristic polynomial p_{G} of S(G) , we use the Faddeev–LeVerrier algorithm (see [ 7 , Chapter IV Section 5] ), throughout which only integers are involved. Computing the coefficients of p_{G}(x-1/\alpha^{*}) can be done entirely within the integral domain \mathbb{Z}[\sqrt{2}] . As a byproduct, the rank of S(G)+I/\alpha^{*} can be computed as n-m , where m is the multiplicity of 0 as a root of p_{G}(x-1/\alpha^{*}) , that is, m is the index such that c_{m}\neq 0 but c_{i}=0 for all i