# stacks/stacks-project

Fetching contributors…
Cannot retrieve contributors at this time
6811 lines (6360 sloc) 204 KB
 \input{preamble} % OK, start here. % \begin{document} \title{Semistable Reduction} \maketitle \phantomsection \label{section-phantom} \tableofcontents \section{Introduction} \label{section-introduction} \noindent In this chapter we prove the semistable reduction theorem for curves. We will use the method of Artin and Winters from their paper \cite{Artin-Winters}. \medskip\noindent It turns out that one can prove the semistable reduction theorem for curves without any results on desingularization. Namely, there is a way to establish the existence and projectivity of moduli of semistable curves using Geometric Invariant Theory (GIT) as developed by Mumford, see \cite{GIT}. This method was championed by Gieseker who proved the full result in his lecture notes \cite{Gieseker}\footnote{Gieseker's lecture notes are written over an algebraically closed field, but the same method works over $\mathbf{Z}$.}. This is quite an amazing feat: it seems somewhat counter intuitive that one can prove such a result without ever truly studying families curves over a positive dimensional base. \medskip\noindent Historically the first proof of the semistable reduction theorem for curves can be found in the paper \cite{DM} by Deligne and Mumford. It proves the theorem by reducing the problem to the case of Abelian varieties which was already known at the time thanks to Grothendieck and others, see \cite{SGA7-I} and \cite{SGA7-II}). The semistable reduction theorem for abelian varieties uses the theory of N\'eron models which in turn rests on a treatment of birational group laws over a base. \medskip\noindent The method in the paper by Artin and Winters relies on desingularization of singularities of surfaces to obtain regular models. Given the existence of regular models, the proof consists in analyzing the possibilities for the special fibre and concluding using an inequality for torsion in the Picard group of a $1$-dimensional scheme over a field. A similar argument can be found in a paper \cite{Saito} of Saito who uses \'etale cohomology directly and who obtains a stronger result in that he can characterize semistable reduction in terms of the action of the inertia on $\ell$-adic \'etale cohomology. \medskip\noindent A different approach one can use to prove the theorem is to use rigid analytic geometry techniques. Here we refer the reader to \cite{vanderPut} and \cite{Arzdorf-Wewers}. \medskip\noindent The paper \cite{Temkin} by Temkin uses valuation theoretic techniques (and proves a lot more besides); also Appendix A of this paper gives a nice overview of the different proofs and the relationship with desingularizations of $2$ dimensional schemes. \medskip\noindent Another overview paper that the reader may wish to consult is \cite{Abbes-ssr} written by Ahmed Abbes. \section{Linear algebra} \label{section-linear-algebra} \noindent A couple of lemmas we will use later on. \begin{lemma} \label{lemma-recurring} \begin{reference} \cite[Theorem I]{Taussky} \end{reference} Let $A = (a_{ij})$ be a complex $n \times n$ matrix. \begin{enumerate} \item If $|a_{ii}| > \sum_{j \not = i} |a_{ij}|$ for each $i$, then $\det(A)$ is nonzero. \item If there exists a real vector $m = (m_1, \ldots, m_n)$ with $m_i > 0$ such that $|a_{ii} m_i| > \sum_{j \not = i} |a_{ij}m_j|$ for each $i$, then $\det(A)$ is nonzero. \end{enumerate} \end{lemma} \begin{proof} If $A$ is as in (1) and $\det(A) = 0$, then there is a nonzero vector $z$ with $Az = 0$. Choose $r$ with $|z_r|$ maximal. Then $$|a_{rr} z_r| = |\sum\nolimits_{k \not = r} a_{rk}z_k| \leq \sum\nolimits_{k \not = r} |a_{rk}||z_k| \leq |z_r| \sum\nolimits_{k \not = r} |a_{rk}| < |a_{rr}||z_r|$$ which is a contradiction. To prove (2) apply (1) to the matrix $(a_{ij}m_j)$ whose determinant is $m_1 \ldots m_n \det(A)$. \end{proof} \begin{lemma} \label{lemma-recurring-real} Let $A = (a_{ij})$ be a real $n \times n$ matrix with $a_{ij} \geq 0$ for $i \not = j$. Let $m = (m_1, \ldots, m_n)$ be a real vector with $m_i > 0$. For $I \subset \{1, \ldots, n\}$ let $x_I \in \mathbf{R}^n$ be the vector whose $i$th coordinate is $m_i$ if $i \in I$ and $0$ otherwise. If \begin{equation} \label{equation-ineq} -a_{ii}m_i \geq \sum\nolimits_{j \not = i} a_{ij}m_j \end{equation} for each $i$, then $\Ker(A)$ is the vector space spanned by the vectors $x_I$ such that \begin{enumerate} \item $a_{ij} = 0$ for $i \in I$, $j \not \in I$, and \item equality holds in (\ref{equation-ineq}) for $i \in I$. \end{enumerate} \end{lemma} \begin{proof} After replacing $a_{ij}$ by $a_{ij}m_j$ we may assume $m_i = 1$ for all $i$. If $I \subset \{1, \ldots, n\}$ such that (1) and (2) are true, then a simple computation shows that $x_I$ is in the kernel of $A$. Conversely, let $x = (x_1, \ldots, x_n) \in \mathbf{R}^n$ be a nonzero vector in the kernel of $A$. We will show by induction on the number of nonzero coordinates of $x$ that $x$ is in the span of the vectors $x_I$ satisfying (1) and (2). Let $I \subset \{1, \ldots, n\}$ be the set of indices $r$ with $|x_r|$ maximal. For $r \in I$ we have $$|a_{rr} x_r| = |\sum\nolimits_{k \not = r} a_{rk}x_k| \leq \sum\nolimits_{k \not = r} a_{rk}|x_k| \leq |x_r| \sum\nolimits_{k \not = r} a_{rk} \leq |a_{rr}||x_r|$$ Thus equality holds everywhere. In particular, we see that $a_{rk} = 0$ if $r \in I$, $k \not \in I$ and equality holds in (\ref{equation-ineq}) for $r \in I$. Then we see that we can substract a suitable multiple of $x_I$ from $x$ to decrease the number of nonzero coordinates. \end{proof} \begin{lemma} \label{lemma-recurring-symmetric-real} Let $A = (a_{ij})$ be a symmetric real $n \times n$ matrix with $a_{ij} \geq 0$ for $i \not = j$. Let $m = (m_1, \ldots, m_n)$ be a real vector with $m_i > 0$. Assume \begin{enumerate} \item $Am = 0$, \item there is no proper nonempty subset $I \subset \{1, \ldots, n\}$ such that $a_{ij} = 0$ for $i \in I$ and $j \not \in I$. \end{enumerate} Then $x^t A x \leq 0$ with equality if and only if $x = qm$ for some $q \in \mathbf{R}$. \end{lemma} \begin{proof}[First proof] After replacing $a_{ij}$ by $a_{ij}m_im_j$ we may assume $m_i = 1$ for all $i$. Condition (1) means $-a_{ii} = \sum_{j \not = i} a_{ij}$ for all $i$. Recall that $x^tAx = \sum_{i, j} x_ia_{ij}x_j$. Then \begin{align*} \sum\nolimits_{i \not = j} -a_{ij}(x_j - x_i)^2 & = \sum\nolimits_{i \not = j} -a_{ij}x_j^2 + 2a_{ij}x_ix_i - a_{ij}x_i^2 \\ & = \sum\nolimits_j a_{jj} x_j^2 + \sum\nolimits_{i \not = j} 2a_{ij}x_ix_i + \sum\nolimits_j a_{jj} x_i^2 \\ & = 2x^tAx \end{align*} This is clearly $\leq 0$. If equality holds, then let $I$ be the set of indices $i$ with $x_i \not = x_1$. Then $a_{ij} = 0$ for $i \in I$ and $j \not \in I$. Thus $I = \{1, \ldots, n\}$ by condition (2) and $x$ is a multiple of $m = (1, \ldots, 1)$. \end{proof} \begin{proof}[Second proof] The matrix $A$ has real eigenvalues by the spectral theorem. We claim all the eigenvalues are $\leq 0$. Namely, since property (1) means $-a_{ii}m_i = \sum_{j \not = i} a_{ij}m_j$ for all $i$, we find that the matrix $A' = A - \lambda I$ for $\lambda > 0$ satisfies $|a'_{ii}m_i| > \sum a'_{ij}m_j = \sum |a'_{ij}m_j|$ for all $i$. Hence $A'$ is invertible by Lemma \ref{lemma-recurring}. This implies that the symmetric bilinear form $x^tAy$ is semi-negative definite, i.e., $x^tAx \leq 0$ for all $x$. It follows that the kernel of $A$ is equal to the set of vectors $x$ with $x^tAx = 0$. The description of the kernel in Lemma \ref{lemma-recurring-real} gives the final statement of the lemma. \end{proof} \begin{lemma} \label{lemma-orthogonal-direct-sum} Let $L$ be a finite free $\mathbf{Z}$-module endowed with an integral symmetric bilinear positive definite form $\langle\ ,\ \rangle : L \times L \to \mathbf{Z}$. Let $A \subset L$ be a submodule with $L/A$ torsion free. Set $B = \{b \in L \mid \langle a, b\rangle = 0,\ \forall a \in A\}$. Then we have injective maps $$A^\#/A \leftarrow L/(A \oplus B) \rightarrow B^\#/B$$ whose cokernels are quotients of $L^\#/L$. Here $A^\# = \{a' \in A \otimes \mathbf{Q} \mid \langle a, a'\rangle \in \mathbf{Z},\ \forall a \in A\}$ and similarly for $B$ and $L$. \end{lemma} \begin{proof} Observe that $L \otimes \mathbf{Q} = A \otimes \mathbf{Q} \oplus B \otimes \mathbf{Q}$ because the form is nondegenerate on $A$ (by positivity). We denote $\pi_B : L \otimes \mathbf{Q} \to B \otimes \mathbf{Q}$ the projection. Observe that $\pi_B(x) \in B^\#$ for $x \in L$ because the form is integral. This gives an exact sequence $$0 \to A \to L \xrightarrow{\pi_B} B^\# \to Q \to 0$$ where $Q$ is the cokernel of $L \to B^\#$. Observe that $Q$ is a quotient of $L^\#/L$ as the map $L^\# \to B^\#$ is surjective since it is the $\mathbf{Z}$-linear dual to $B \to L$ which is split as a map of $\mathbf{Z}$-modules. Dividing by $A \oplus B$ we get a short exact sequence $$0 \to L/(A \oplus B) \to B^\#/B \to Q \to 0$$ This proves the lemma. \end{proof} \begin{lemma} \label{lemma-coker} Let $L_0$, $L_1$ be a finite free $\mathbf{Z}$-modules endowed with integral symmetric bilinear positive definite forms $\langle\ ,\ \rangle : L_i \times L_i \to \mathbf{Z}$. Let $\text{d} : L_0 \to L_1$ and $\text{d}^* : L_1 \to L_0$ be adjoint. If $\langle\ ,\ \rangle$ on $L_0$ is unimodular, then there is an isomorphism $$\Phi : \Coker(\text{d}^*\text{d})_{torsion} \longrightarrow \Im(\text{d})^\#/\Im(\text{d})$$ with notation as in Lemma \ref{lemma-orthogonal-direct-sum}. \end{lemma} \begin{proof} Let $x \in L_0$ be an element representing a torsion class in $\Coker(\text{d}^*\text{d})$. Then for some $a > 0$ we can write $ax = \text{d}^*\text{d}(y)$. For any $z \in \Im(\text{d})$, say $z = \text{d}(y')$, we have $$\langle (1/a)\text{d}(y), z \rangle = \langle (1/a)\text{d}(y), \text{d}(y') \rangle = \langle x, y' \rangle \in \mathbf{Z}$$ Hence $(1/a)\text{d}(y) \in \Im(\text{d})^\#$. We define $\Phi(x) = (1/a)\text{d}(y) \bmod \Im(\text{d})$. We omit the proof that $\Phi$ is well defined, additive, and injective. \medskip\noindent To prove $\Phi$ is surjective, let $z \in \Im(\text{d})^\#$. Then $z$ defines a linear map $L_0 \to \mathbf{Z}$ by the rule $x \mapsto \langle z, \text{d}(x)\rangle$. Since the pairing on $L_0$ is unimodular by assumption we can find an $x' \in L_0$ with $\langle x', x \rangle = \langle z, \text{d}(x)\rangle$ for all $x \in L_0$. In particular, we see that $x'$ pairs to zero with $\Ker(\text{d})$. Since $\Im(\text{d}^*\text{d}) \otimes \mathbf{Q}$ is the orthogonal complement of $\Ker(\text{d}) \otimes \mathbf{Q}$ this means that $x'$ defines a torsion class in $\Coker(\text{d}^*\text{d})$. We claim that $\Phi(x') = z$. Namely, write $a x' = \text{d}^*\text{d}(y)$ for some $y \in L_0$ and $a > 0$. For any $x \in L_0$ we get $$\langle z, \text{d}(x)\rangle = \langle x', x \rangle = \langle (1/a)\text{d}^*\text{d}(y), x \rangle = \langle (1/a)\text{d}(y),\text{d}(x) \rangle$$ Hence $z = \Phi(x')$ and the proof is complete. \end{proof} \begin{lemma} \label{lemma-recurring-symmetric-integer} Let $A = (a_{ij})$ be a symmetric $n \times n$ integer matrix with $a_{ij} \geq 0$ for $i \not = j$. Let $m = (m_1, \ldots, m_n)$ be an integer vector with $m_i > 0$. Assume \begin{enumerate} \item $Am = 0$, \item there is no proper nonempty subset $I \subset \{1, \ldots, n\}$ such that $a_{ij} = 0$ for $i \in I$ and $j \not \in I$. \end{enumerate} Let $e$ be the number of pairs $(i, j)$ with $i < j$ and $a_{ij} > 0$. Then for $\ell$ a prime number coprime with all $a_{ij}$ and $m_i$ we have $$\dim_{\mathbf{F}_\ell}(\Coker(A)[\ell]) \leq 1 - n + e$$ \end{lemma} \begin{proof} By Lemma \ref{lemma-recurring-symmetric-real} the rank of $A$ is $n - 1$. The composition $$\mathbf{Z}^{\oplus n} \xrightarrow{\text{diag}(m_1, \ldots, m_n)} \mathbf{Z}^{\oplus n} \xrightarrow{(a_{ij})} \mathbf{Z}^{\oplus n} \xrightarrow{\text{diag}(m_1, \ldots, m_n)} \mathbf{Z}^{\oplus n}$$ has matrix $a_{ij}m_im_j$. Since the cokernel of the first and last maps are torsion of order prime to $\ell$ by our restriction on $\ell$ we see that it suffices to prove the lemma for the matrix with entries $a_{ij}m_im_j$. Thus we may assume $m = (1, \ldots, 1)$. \medskip\noindent Assume $m = (1, \ldots, 1)$. Set $V = \{1, \ldots, n\}$ and $E = \{(i, j) \mid i < j\text{ and }a_{ij}> 0\}$. For $e = (i, j) \in E$ set $a_e = a_{ij}$. Define maps $s, t : E \to V$ by setting $s(i, j) = i$ and $t(i, j) = j$. Set $\mathbf{Z}(V) = \bigoplus_{i \in V} \mathbf{Z}i$ and $\mathbf{Z}(E) = \bigoplus_{e \in E} \mathbf{Z}e$. We define symmetric positive definite integer valued pairings on $\mathbf{Z}(V)$ and $\mathbf{Z}(E)$ by setting $$\langle i, i \rangle = 1\text{ for }i \in V, \quad \langle e, e \rangle = a_e\text{ for }e \in E$$ and all other pairings zero. Consider the maps $$\text{d} : \mathbf{Z}(V) \to \mathbf{Z}(E), \quad i \longmapsto \sum\nolimits_{e \in E,\ s(e) = i} e - \sum\nolimits_{e \in E,\ t(e) = i} e$$ and $$\text{d}^*(e) = a_e(s(e) - t(e))$$ A computation shows that $$\langle d(x), y\rangle = \langle x, \text{d}^*(y) \rangle$$ in other words, $\text{d}$ and $\text{d}^*$ are adjoint. Next we compute \begin{align*} \text{d}^*\text{d}(i) & = \text{d}^*( \sum\nolimits_{e \in E,\ s(e) = i} e - \sum\nolimits_{e \in E,\ t(e) = i} e) \\ & = \sum\nolimits_{e \in E,\ s(e) = i} a_e(s(e) - t(e)) - \sum\nolimits_{e \in E,\ t(e) = i} a_e(s(e) - t(e)) \end{align*} The coefficient of $i$ in $\text{d}^*\text{d}(i)$ is $$\sum\nolimits_{e \in E,\ s(e) = i} a_e + \sum\nolimits_{e \in E,\ t(e) = i} a_e = - a_{ii}$$ because $\sum_j a_{ij} = 0$ and the coefficient of $j \not = i$ in $\text{d}^*\text{d}(i)$ is $-a_{ij}$. Hence $\Coker(A) = \Coker(\text{d}^*\text{d})$. \medskip\noindent Consider the inclusion $$\Im(\text{d}) \oplus \Ker(\text{d}^*) \subset \mathbf{Z}(E)$$ The left hand side is an orthogonal direct sum. Clearly $\mathbf{Z}(E)/\Ker(\text{d}^*)$ is torsion free. We claim $\mathbf{Z}(E)/\Im(\text{d})$ is torsion free as well. Namely, say $x = \sum x_e e \in \mathbf{Z}(E)$ and $a > 1$ are such that $ax = \text{d}y$ for some $y = \sum y_i i \in \mathbf{Z}(V)$. Then $a x_e = y_{s(e)} - y_{t(e)}$. By property (2) we conclude that all $y_i$ have the same congruence class modulo $a$. Hence we can write $y = a y' + (y_1, y_1, \ldots, y_1)$. Since $\text{d}(y_1, y_1, \ldots, y_1) = 0$ we conclude that $x = \text{d}(y')$ which is what we had to show. \medskip\noindent Hence we may apply Lemma \ref{lemma-orthogonal-direct-sum} to get injective maps $$\Im(\text{d})^\#/\Im(\text{d}) \leftarrow \mathbf{Z}(E)/(\Im(\text{d}) \oplus \Ker(\text{d}^*)) \rightarrow \Ker(\text{d}^*)^\#/\Ker(\text{d}^*)$$ whose cokernels are annihilated by the product of the $a_e$ (which is prime to $\ell$). Since $\Ker(\text{d}^*)$ is a lattice of rank $1 - n + e$ we see that the proof is complete if we prove that there exists an isomorphism $$\Phi : M_{torsion} \longrightarrow \Im(\text{d})^\#/\Im(\text{d})$$ This is proved in Lemma \ref{lemma-coker}. \end{proof} \section{Numerical types} \label{section-numerical-types} \noindent Part of the arguments will involve the combinatorics of the following data structures. \begin{definition} \label{definition-type} A {\it numerical type} $T$ is given by $$n, m_i, a_{ij}, w_i, g_i$$ where $n \geq 1$ is an integer and $m_i$, $a_{ij}$, $w_i$, $g_i$ are integers for $1 \leq i, j \leq n$ subject to the following conditions \begin{enumerate} \item $m_i > 0$, $w_i > 0$, $g_i \geq 0$, \item the matrix $A = (a_{ij})$ is symmetric and $a_{ij} \geq 0$ for $i \not = j$, \item there is no proper nonempty subset $I \subset \{1, \ldots, n\}$ such that $a_{ij} = 0$ for $i \in I$, $j \not \in I$, \item for each $i$ we have $\sum_j a_{ij}m_j = 0$, and \item $w_i | a_{ij}$. \end{enumerate} \end{definition} \noindent This is obviously a somewhat annoying type of structure to work with, but it is exactly what shows up in special fibres of proper regular models of smooth geometrically connected curves. Of course we only care about these types up to reordering the indices. \begin{definition} \label{definition-type-equivalent} We say two numerical types $n, m_i, a_{ij}, w_i, g_i$ and $n', m'_i, a'_{ij}, w'_i, g'_i$ are {\it equivalent types} if there exists a permutation $\sigma$ of $\{1, \ldots, n\}$ such that $m_i = m'_{\sigma(i)}$, $a_{ij} = a'_{\sigma(i)\sigma(j)}$, $w_i = w'_{\sigma(i)}$, and $g_i = g'_{\sigma(i)}$. \end{definition} \noindent A numerical type has a genus. \begin{lemma} \label{lemma-genus} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type. Then the expression $$g = 1 + \sum m_i(w_i(g_i - 1) - \frac{1}{2} a_{ii})$$ is an integer. \end{lemma} \begin{proof} To prove $g$ is an integer we have to show that $\sum a_{ii}m_i$ is even. This we can see by computing modulo $2$ as follows \begin{align*} \sum\nolimits_i a_{ii} m_i & \equiv \sum\nolimits_{i,\ m_i\text{ odd}} a_{ii}m_i \\ & \equiv \sum\nolimits_{i,\ m_i\text{ odd}} \sum\nolimits_{j \not = i} a_{ij}m_j \\ & \equiv \sum\nolimits_{i,\ m_i\text{ odd}} \sum\nolimits_{j \not = i,\ m_j\text{ odd}} a_{ij}m_j \\ & \equiv \sum\nolimits_{i < j,\ m_i\text{ and }m_j\text{ odd}} a_{ij}(m_i + m_j) \\ & \equiv 0 \end{align*} where we have used that $a_{ij} = a_{ji}$ and that $\sum_j a_{ij}m_j = 0$ for all $i$. \end{proof} \begin{definition} \label{definition-genus} We say $n, m_i, a_{ij}, w_i, g_i$ is a {\it numerical type of genus $g$} if $g = 1 + \sum m_i(w_i(g_i - 1) - \frac{1}{2} a_{ii})$ is the integer from Lemma \ref{lemma-genus}. \end{definition} \noindent We will prove below (Lemma \ref{lemma-genus-nonnegative}) that the genus is almost always $\geq 0$. But you can have numerical types with negative genus. \begin{lemma} \label{lemma-irreducible} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type of genus $g$. If $n = 1$, then $a_{11} = 0$ and $g = 1 + m_1w_1(g_1 - 1)$. Moreover, we can classify all such numerical types as follows \begin{enumerate} \item If $g < 0$, then $g_1 = 0$ and there are finitely many possible numerical types of genus $g$ with $n = 1$ corresponding to factorizations $m_1w_1 = 1 - g$. \item If $g = 0$, then $m_1 = 1$, $w_1 = 1$, $g_1 = 0$ as in Lemma \ref{lemma-genus-zero}. \item If $g = 1$, then we conclude $g_1 = 1$ but $m_1, w_1$ can be arbitrary positive integers; this is case (\ref{item-one}) of Lemma \ref{lemma-genus-one}. \item If $g > 1$, then $g_1 > 1$ and there are finitely many possible numerical types of genus $g$ with $n = 1$ corresponding to factorizations $m_1w_1(g_1 - 1) = g - 1$. \end{enumerate} \end{lemma} \begin{proof} The lemma proves itself. \end{proof} \begin{lemma} \label{lemma-diagonal-negative} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type of genus $g$. If $n > 1$, then $a_{ii} < 0$ for all $i$. \end{lemma} \begin{proof} Lemma \ref{lemma-recurring-symmetric-real} applies to the matrix $A$. \end{proof} \begin{lemma} \label{lemma-minus-one} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type of genus $g$. Assume $n > 1$. If $i$ is such that the contribution $m_i(w_i(g_i - 1) - \frac{1}{2} a_{ii})$ to the genus $g$ is $< 0$, then $g_i = 0$ and $a_{ii} = -w_i$. \end{lemma} \begin{proof} Follows immediately from Lemma \ref{lemma-diagonal-negative} and $w_i > 0$, $g_i \geq 0$, and $w_i | a_{ii}$. \end{proof} \begin{definition} \label{definition-type-minus-one} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type. We say $i$ is a {\it $(-1)$-index} if $g_i = 0$ and $a_{ii} = -w_i$. \end{definition} \noindent We can contract'' $(-1)$-indices. \begin{lemma} \label{lemma-contract} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type $T$. Assume $n$ is a $(-1)$-index. Then there is a numerical type $T'$ given by $n', m'_i, a'_{ij}, w'_i, g'_i$ with \begin{enumerate} \item $n' = n - 1$, \item $m'_i = m_i$, \item $a'_{ij} = a_{ij} - a_{in}a_{jn}/a_{nn}$, \item $w'_i = w_i/2$ if $a_{in}/w_n$ even and $a_{in}/w_i$ odd and $w'_i = w_i$ else, \item $g'_i = \frac{w_i}{w'_i}(g_i - 1) + 1 + \frac{a_{in}^2 - w_na_{in}}{2w'_iw_n}$. \end{enumerate} Moreover, we have $g = g'$. \end{lemma} \begin{proof} Observe that $n > 1$ for example by Lemma \ref{lemma-irreducible} and hence $n' \geq 1$. We check conditions (1) -- (5) of Definition \ref{definition-type} for $n', m'_i, a'_{ij}, w'_i, g'_i$. \medskip\noindent Condition (1) is immediate. \medskip\noindent Condition (2). Symmetry of $A' = (a'_{ij})$ is immediate and since $a_{nn} < 0$ by Lemma \ref{lemma-diagonal-negative} we see that $a'_{ij} \geq a_{ij} \geq 0$ if $i \not = j$. \medskip\noindent Condition (3). Suppose that $I \subset \{1, \ldots, n - 1\}$ such that $a'_{ii'} = 0$ for $i \in I$ and $i' \in \{1, \ldots, n - 1\} \setminus I$. Then we see that for each $i \in I$ and $i' \in I'$ we have $a_{in}a_{i'n} = 0$. Thus either $a_{in} = 0$ for all $i \in I$ and $I \subset \{1, \ldots, n\}$ is a contradiction for property (3) for $T$, or $a_{i'n} = 0$ for all $i' \in \{1, \ldots, n - 1\} \setminus I$ and $I \cup \{n\} \subset \{1, \ldots, n\}$ is a contradiction for property (3) of $T$. Hence (3) holds for $T'$. \medskip\noindent Condition (4). We compute $$\sum\nolimits_{j = 1}^{n - 1} a'_{ij}m_j = \sum\nolimits_{j = 1}^{n - 1} (a_{ij}m_j - \frac{a_{in}a_{jn}m_j}{a_{nn}}) = - a_{in}m_n - \frac{a_{in}}{a_{nn}}(-a_{nn}m_n) = 0$$ as desired. \medskip\noindent Condition (5). We have to show that $w'_i$ divides $a_{in}a_{jn}/a_{nn}$. This is clear because $a_{nn} = -w_n$ and $w_n | a_{jn}$ and $w_i | a_{in}$. \medskip\noindent To show that $g = g'$ we first write \begin{align*} g & = 1 + \sum\nolimits_{i = 1}^n m_i(w_i(g_i - 1) - \frac{1}{2}a_{ii}) \\ & = 1 + \sum\nolimits_{i = 1}^{n - 1} m_i(w_i(g_i - 1) - \frac{1}{2}a_{ii}) -\frac{1}{2}m_nw_n \\ & = 1 + \sum\nolimits_{i = 1}^{n - 1} m_i(w_i(g_i - 1) - \frac{1}{2}a_{ii} - \frac{1}{2}a_{in}) \end{align*} Comparing with the expression for $g'$ we see that it suffices if $$w'_i(g'_i - 1) - \frac{1}{2}a'_{ii} = w_i(g_i - 1) - \frac{1}{2}a_{in} - \frac{1}{2}a_{ii}$$ for $i \leq n - 1$. In other words, we have $$g'_i = \frac{2w_i(g_i - 1) - a_{in} - a_{ii} + a'_{ii} + 2w'_i}{2w'_i} = \frac{w_i}{w'_i}(g_i - 1) + 1 + \frac{a_{in}^2 - w_na_{in}}{2w'_iw_n}$$ It is elementary to check that this is an integer $\geq 0$ if we choose $w'_i$ as in (4). \end{proof} \begin{lemma} \label{lemma-top-genus} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type. Let $e$ be the number of pairs $(i, j)$ with $i < j$ and $a_{ij} > 0$. Then the expression $g_{top} = 1 - n + e$ is $\geq 0$. \end{lemma} \begin{proof} If not, then $e < n - 1$ which means there exists an $i$ such that $a_{ij} = 0$ for all $j \not = i$. This contradicts assumption (3) of Definition \ref{definition-type}. \end{proof} \begin{definition} \label{definition-top-genus} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type $T$. The {\it topological genus of $T$} is the nonnegative integer $g_{top} = 1 - n + e$ from Lemma \ref{lemma-top-genus}. \end{definition} \noindent We want to bound the genus by the topological genus. However, this will not always be the case, for example for numerical types with $n = 1$ as in Lemma \ref{lemma-irreducible}. But it will be true for minimal numerical types which are defined as follows. \begin{definition} \label{definition-type-minimal} We say the numerical type $n, m_i, a_{ij}, w_i, g_i$ of genus $g$ is {\it minimal} if there does not exist an $i$ with $g_i = 0$ and $a_{ii} = -w_i$, in other words, if there does not exist a $(-1)$-index. \end{definition} \noindent We will prove that the genus $g$ of a minimal type with $n > 1$ is greater than or equal to $\max(1, g_{top})$. \begin{lemma} \label{lemma-non-irreducible-minimal-type-genus-at-least-one} If $n, m_i, a_{ij}, w_i, g_i$ is a minimal numerical type with $n > 1$, then $g \geq 1$. \end{lemma} \begin{proof} This is true because $g = 1 + \sum \Phi_i$ with $\Phi_i = m_i(w_i(g_i - 1) - \frac{1}{2} a_{ii})$ nonnegative by Lemma \ref{lemma-minus-one} and the definition of minimal types. \end{proof} \begin{lemma} \label{lemma-genus-nonnegative} If $n, m_i, a_{ij}, w_i, g_i$ is a minimal numerical type with $n > 1$, then $g \geq g_{top}$. \end{lemma} \begin{proof} The reader who is only interested in the case of numerical types associated to proper regular models can skip this proof as we will reprove this in the geometric situation later. We can write $$g_{top} = 1 - n + \frac{1}{2}\sum\nolimits_{a_{ij} > 0} 1 = 1 + \sum\nolimits_i (-1 + \frac{1}{2}\sum\nolimits_{j \not = i,\ a_{ij} > 0} 1)$$ On the other hand, we have \begin{align*} g & = 1 + \sum m_i(w_i(g_i - 1) - \frac{1}{2} a_{ii}) \\ & = 1 + \sum m_iw_ig_i - \sum m_iw_i + \frac{1}{2} \sum\nolimits_{i \not = j} a_{ij}m_j \\ & = 1 + \sum\nolimits_i m_iw_i(-1 + g_i + \frac{1}{2} \sum\nolimits_{j \not = i} \frac{a_{ij}}{w_i}) \end{align*} The first equality is the definition, the second equality uses that $\sum a_{ij}m_j = 0$, and the last equality uses that uses $a_{ij} = a_{ji}$ and switching order of summation. Comparing with the formula for $g_{top}$ we conclude that the lemma holds if $$\Psi_i = m_iw_i(-1 + g_i + \frac{1}{2} \sum\nolimits_{j \not = i} \frac{a_{ij}}{w_i}) - (-1 + \frac{1}{2}\sum\nolimits_{j \not = i,\ a_{ij} > 0} 1)$$ is $\geq 0$ for each $i$. However, this may not be the case. Let us analyze for which indices we can have $\Psi_i < 0$. First, observe that $$(-1 + g_i + \frac{1}{2}\sum\nolimits_{j \not = i} \frac{a_{ij}}{w_i}) \geq (-1 + \frac{1}{2}\sum\nolimits_{j \not = i,\ a_{ij} > 0} 1)$$ because $a_{ij}/w_i$ is a nonnegative integer. Since $m_iw_i$ is a positive integer we conclude that $\Psi_i \geq 0$ as soon as either $m_iw_i = 1$ or the left hand side of the inequality is $\geq 0$ which happens if $g_i > 0$, or $a_{ij} > 0$ for at least two indices $j$, or if there is a $j$ with $a_{ij} > w_i$. Thus $$P = \{i : \Psi_i < 0\}$$ is the set of indices $i$ such that $m_iw_i > 1$, $g_i = 0$, $a_{ij} > 0$ for a unique $j$, and $a_{ij} = w_i$ for this $j$. Moreover $$i \in P \Rightarrow \Psi_i = \frac{1}{2}(-m_iw_i + 1)$$ The strategy of proof is to show that given $i \in P$ we can borrow a bit from $\Psi_j$ where $j$ is the neighbour of $i$, i.e., $a_{ij} > 0$. However, this won't quite work because $j$ may be an index with $\Psi_j = 0$. \medskip\noindent Consider the set $$Z = \{j : g_j = 0\text{ and } j\text{ has exactly two neighbours }i, k\text{ with } a_{ij} = w_j = a_{jk}\}$$ For $j \in Z$ we have $\Psi_j = 0$. We will consider sequences $M = (i, j_1, \ldots, j_s)$ where $s \geq 0$, $i \in P$, $j_1, \ldots, j_s \in Z$, and $a_{ij_1} > 0, a_{j_1j_2} > 0, \ldots, a_{j_{s - 1}j_s} > 0$. If our numerical type consists of two indices which are in $P$ or more generally if our numerical type consists of two indices which are in $P$ and all other indices in $Z$, then $g_{top} = 0$ and we win by Lemma \ref{lemma-non-irreducible-minimal-type-genus-at-least-one}. We may and do discard these cases. \medskip\noindent Let $M = (i, j_1, \ldots, j_s)$ be a maximal sequence and let $k$ be the second neighbour of $j_s$. (If $s = 0$, then $k$ is the unique neighbour of $i$.) By maximality $k \not \in Z$ and by what we just said $k \not \in P$. Observe that $w_i = a_{ij_1} = w_{j_1} = a_{j_1j_2} = \ldots = w_{j_s} = a_{j_sk}$. Looking at the definition of a numerical type we see that \begin{align*} m_ia_{ii} + m_{j_1}w_i & = 0,\\ m_iw_i + m_{j_1}a_{j_1j_1} + m_{j_2}w_i & = 0,\\ \ldots & \ldots \\ m_{j_{s - 1}}w_i + m_{j_s}a_{j_sj_s} + m_kw_i & = 0 \end{align*} The first equality implies $m_{j_1} \geq 2m_i$ because the numerical type is minimal. Then the second equality implies $m_{j_2} \geq 3m_i$, and so on. In any case, we conclude that $m_k \geq 2m_i$ (including when $s = 0$). \medskip\noindent Let $k$ be an index such that we have a $t > 0$ and pairwise distinct maximal sequences $M_1, \ldots, M_t$ as above, with $M_b = (i_b, j_{b, 1}, \ldots, j_{b, s_b})$ such that $k$ is a neighbour of $j_{b, s_b}$ for $b = 1, \ldots, t$. We will show that $\Phi_j + \sum_{b = 1, \ldots, t} \Phi_{i_b} \geq 0$. This will finish the proof of the lemma by what we said above. Let $M$ be the union of the indices occurring in $M_b$, $b = 1, \ldots, t$. We write $$\Psi_k = -\sum\nolimits_{b = 1, \ldots, t} \Psi_{i_b} + \Psi_k'$$ where \begin{align*} \Psi_k' & = m_kw_k\left(-1 + g_k + \frac{1}{2} \sum\nolimits_{b = 1, \ldots t} (\frac{a_{kj_{b, s_b}}}{w_k} - \frac{m_{i_b}w_{i_b}}{m_kw_k}) + \frac{1}{2} \sum\nolimits_{l \not = k,\ l \not \in M} \frac{a_{kl}}{w_k} \right) \\ & -\left( -1 + \frac{1}{2}\sum\nolimits_{l \not = k,\ l \not \in M,\ a_{kl} > 0} 1 \right) \end{align*} Assume $\Psi_k' < 0$ to get a contradiction. If the set $\{l : l \not = k,\ l \not \in M,\ a_{kl} > 0\}$ is empty, then $\{1, \ldots, n\} = M \cup \{k\}$ and $g_{top} = 0$ because $e = n - 1$ in this case and the result holds by Lemma \ref{lemma-non-irreducible-minimal-type-genus-at-least-one}. Thus we may assume there is at least one such $l$ which contributes $(1/2)a_{kl}/w_k \geq 1/2$ to the sum inside the first brackets. For each $b = 1, \ldots, t$ we have $$\frac{a_{kj_{b, s_b}}}{w_k} - \frac{m_{i_b}w_{i_b}}{m_kw_k} = \frac{w_{i_b}}{w_k}(1 - \frac{m_{i_b}}{m_k})$$ This expression is $\geq \frac{1}{2}$ because $m_k \geq 2m_{i_b}$ by the previous paragraph and is $\geq 1$ if $w_k < w_{i_b}$. It follows that $\Psi_k' < 0$ implies $g_k = 0$. If $t \geq 2$ or $t = 1$ and $w_k < w_{i_1}$, then $\Psi_k' \geq 0$ (here we use the existence of an $l$ as shown above) which is a contradiction too. Thus $t = 1$ and $w_k = w_{i_1}$. If there at least two nonzero terms in the sum over $l$ or if there is one such $k$ and $a_{kl} > w_k$, then $\Psi_k' \geq 0$ as well. The final possibility is that $t = 1$ and there is one $l$ with $a_{kl} = w_k$. This is disallowed as this would mean $k \in Z$ contradicting the maximality of $M_1$. \end{proof} \begin{lemma} \label{lemma-minus-two} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type of genus $g$. Assume $n > 1$. If $i$ is such that the contribution $m_i(w_i(g_i - 1) - \frac{1}{2} a_{ii})$ to the genus $g$ is $0$, then $g_i = 0$ and $a_{ii} = -2w_i$. \end{lemma} \begin{proof} Follows immediately from Lemma \ref{lemma-diagonal-negative} and $w_i > 0$, $g_i \geq 0$, and $w_i | a_{ii}$. \end{proof} \noindent It turns out that the indices satisfying this relation play an important role in the structure of minimal numerical types. Hence we give them a name. \begin{definition} \label{definition-type-minus-two} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type of genus $g$. We say $i$ is a {\it $(-2)$-index} if $g_i = 0$ and $a_{ii} = -2w_i$. \end{definition} \noindent Given a minimal numerical type of genus $g$ the $(-2)$-indices are exactly the indices which do not contribute a positive number to the genus in the formula $$g = 1 + \sum m_i(w_i(g_i - 1) - \frac{1}{2} a_{ii})$$ Thus it will be somewhat tricky to bound the quantities associated with $(-2)$-indices as we will see later. \begin{remark} \label{remark-genus-equality} Let $n, m_i, a_{ij}, w_i, g_i$ be a minimal numerical type with $n > 1$. Equality $g = g_{top}$ can hold in Lemma \ref{lemma-genus-nonnegative}. For example, if $m_i = w_i = 1$ and $g_i = 0$ for all $i$ and $a_{ij} \in \{0, 1\}$ for $i < j$. \end{remark} \section{The Picard group of a numerical type} \label{section-picard-group} \noindent Here is the definition. \begin{definition} \label{definition-picard-group} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type $T$. The {\it Picard group of $T$} is the cokernel of the matrix $(a_{ij}/w_i)$, more precisely $$\text{Pic}(T) = \Coker\left( \mathbf{Z}^{\oplus n} \to \mathbf{Z}^{\oplus n},\quad e_i \mapsto \sum \frac{a_{ij}}{w_j}e_j \right)$$ where $e_i$ denotes the $i$th standard basis vector for $\mathbf{Z}^{\oplus n}$. \end{definition} \begin{lemma} \label{lemma-picard-rank-1} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type $T$. The Picard group of $T$ is a finitely generated abelian group of rank $1$. \end{lemma} \begin{proof} If $n = 1$, then $A = (a_{ij})$ is the zero matrix and the result is clear. For $n > 1$ the matrix $A$ has rank $n - 1$ by either Lemma \ref{lemma-recurring-real} or Lemma \ref{lemma-recurring-symmetric-real}. Of course the rank is not affected by scaling the rows by $1/w_i$. This proves the lemma. \end{proof} \begin{lemma} \label{lemma-picard-T-and-A} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type $T$. Then $\text{Pic}(T) \subset \Coker(A)$ where $A = (a_{ij})$. \end{lemma} \begin{proof} Since $\text{Pic}(T)$ is the cokernel of $(a_{ij}/w_i)$ we see that there is a commutative diagram $$\xymatrix{ 0 \ar[r] & \mathbf{Z}^{\oplus n} \ar[rr]_A & & \mathbf{Z}^{\oplus n} \ar[rr] & & \Coker(A) \ar[r] & 0 \\ 0 \ar[r] & \mathbf{Z}^{\oplus n} \ar[rr]^{(a_{ij}/w_i)} \ar[u]_{\text{id}} & & \mathbf{Z}^{\oplus n} \ar[rr] \ar[u]_{\text{diag}(w_1, \ldots, w_n)} & & \text{Pic}(T) \ar[r] \ar[u] & 0 }$$ with exact rows. By the snake lemma we conclude that $\text{Pic}(T) \subset \Coker(A)$. \end{proof} \begin{lemma} \label{lemma-contract-picard-group} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type $T$. Assume $n$ is a $(-1)$-index. Let $T'$ be the numerical type constructed in Lemma \ref{lemma-contract}. There exists an injective map $$\text{Pic}(T) \to \text{Pic}(T')$$ whose cokernel is an elementary abelian $2$-group. \end{lemma} \begin{proof} Recall that $n' = n - 1$. Let $e_i$, resp., $e'_i$ be the $i$th basis vector of $\mathbf{Z}^{\oplus n}$, resp.\ $\mathbf{Z}^{\oplus n - 1}$. First we denote $$q : \mathbf{Z}^{\oplus n} \to \mathbf{Z}^{\oplus n - 1}, \quad e_n \mapsto 0\text{ and }e_i \mapsto e'_i\text{ for }i \leq n - 1$$ and we set $$p : \mathbf{Z}^{\oplus n} \to \mathbf{Z}^{\oplus n - 1},\quad e_n \mapsto \sum\nolimits_{j = 1}^{n - 1} \frac{a_{nj}}{w'_j} e'_j \text{ and } e_i \mapsto \frac{w_i}{w'_i} e'_i\text{ for }i \leq n - 1$$ A computation (which we omit) shows there is a commutative diagram $$\xymatrix{ \mathbf{Z}^{\oplus n} \ar[rr]_{(a_{ij}/w_i)} \ar[d]_q & & \mathbf{Z}^{\oplus n} \ar[d]^p \\ \mathbf{Z}^{\oplus n'} \ar[rr]^{(a'_{ij}/w'_i)} & & \mathbf{Z}^{\oplus n'} }$$ Since the cokernel of the top arrow is $\text{Pic}(T)$ and the cokernel of the bottom arrow is $\text{Pic}(T')$, we obtain the desired homomorphism of Picard groups. Since $\frac{w_i}{w'_i} \in \{1, 2\}$ we see that the cokernel of $\text{Pic}(T) \to \text{Pic}(T')$ is annihilated by $2$ (because $2e'_i$ is in the image of $p$ for all $i \leq n - 1$). Finally, we show $\text{Pic}(T) \to \text{Pic}(T')$ is injective. Let $L = (l_1, \ldots, l_n)$ be a representative of an element of $\text{Pic}(T)$ mapping to zero in $\text{Pic}(T')$. Since $q$ is surjective, a diagram chase shows that we can assume $L$ is in the kernel of $p$. This means that $l_na_{ni}/w'_i + l_iw_i/w'_i = 0$, i.e., $l_i = - a_{ni}/w_i l_n$. Thus $L$ is the image of $-l_ne_n$ under the map $(a_{ij}/w_j)$ and the lemma is proved. \end{proof} \begin{lemma} \label{lemma-picard-group-genus-nonpositive} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type $T$. If the genus $g$ of $T$ is $\leq 0$, then $\text{Pic}(T) = \mathbf{Z}$. \end{lemma} \begin{proof} By induction on $n$. If $n = 1$, then the assertion is clear. If $n > 1$, then $T$ is not minimal by Lemma \ref{lemma-non-irreducible-minimal-type-genus-at-least-one}. After replacing $T$ by an equivalent type we may assume $n$ is a $(-1)$-index. By Lemma \ref{lemma-contract-picard-group} we find $\text{Pic}(T) \subset \text{Pic}(T')$. By Lemma \ref{lemma-contract} we see that the genus of $T'$ is equal to the genus of $T$ and we conclude by induction. \end{proof} \section{Classification of proper subgraphs} \label{section-classify-proper-subgraphs} \noindent In this section we assume given a numerical type $n, m_i, a_{ij}, w_i, g_i$ of genus $g$. We will find a complete list of possible subgraphs'' consisting entirely of $(-2)$-indices (Definition \ref{definition-type-minus-two}) and at the same time we classify all possible minimal numerical types of genus $1$. In other words, in this section we prove Proposition \ref{proposition-classify-subgraphs} and Lemma \ref{lemma-genus-one} \medskip\noindent Our strategy will be as follows. Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type of genus $g$. Let $I \subset \{1, \ldots, n\}$ be a subset consisting of $(-2)$-indices such that there does not exist a nonempty proper subset $J \subset I$ with $a_{jj'} = 0$ for $j \in J$, $j' \in I \setminus J$. We work by induction on the cardinality $|I|$ of $I$. If $I = \{i\}$ consists of $1$ index, then the only constraints on $m_i$, $a_{ii}$, and $w_i$ are $w_i | a_{ii}$ from Definition \ref{definition-type} and $a_{ii} < 0$ from Lemma \ref{lemma-diagonal-negative}. and this will serve as our base case. In the induction step we first apply the induction hypothesis to subsets $I' \subset I$ of size $|I'| < |I|$. This will put some constraints on the possible $m_i, a_{ij}, w_i$, $i, j \in I$. In particular, since $|I'| < |I| \leq n$ it will follow from $\sum a_{ij}m_j = 0$ and Lemma \ref{lemma-recurring-symmetric-real} that the sub matrices $(a_{ij})_{i, j \in I'}$ are negative definite and their determinant will have sign $(-1)^m$. For each possibility left over we compute the determinant of $(a_{ij})_{i, j \in I}$. If the determinant has sign $-(-1)^{|I|}$ then this case can be discarded because Sylvester's theorem tells us the matrix $(a_{ij})_{i, j \in I}$ is not negative semi-definite. If the determinant has sign $(-1)^{|I|}$, then $|I| < n$ and we (tentatively) conclude this case can occur as a possible proper subgraph and we list it in one of the lemmas in this section. If the determinant is $0$, then we must have $|I| = n$ (by Lemma \ref{lemma-recurring-symmetric-real} again) and $g = 0$. In these cases we actually find all possible $m_i, a_{ij}, w_i$, $i, j \in I$ and list them in Lemma \ref{lemma-genus-one}. After completing the argument we obtain all possible minimal numerical types of genus $1$ with $n > 1$ because each of these necessarily consists entirely of $(-2)$-indices (and hence will show up in the induction process) by the formula for the genus and the remarks in the previous section. At the very end of the day the reader can go through the list of possibilities given in Lemma \ref{lemma-genus-one} to see that all configurations of proper subgraphs listed in this section as possible do in fact occur already for numerical types of genus $1$. \medskip\noindent Suppose that $i$ and $j$ are $(-2)$-indices with $a_{ij} > 0$. Since the matrix $A = (a_{ij})$ is semi-negative definite by Lemma \ref{lemma-recurring-symmetric-real} we see that the matrix $$\left( \begin{matrix} -2w_i & a_{ij} \\ a_{ij} & -2w_j \end{matrix} \right)$$ is negative definite unless $n = 2$. The case $n = 2$ can happen: then the determinant $4w_1w_2 - a_{12}^2$ is zero. Using that $\text{lcm}(w_1, w_2)$ divides $a_{12}$ the reader easily finds that the only possibilities are $$(w_1, w_2, a_{12}) = (w, w, 2w), (w, 4w, 4w), \text{ or }(4w, w, 4w)$$ Observe that the case $(4w, w, 4w)$ is obtained from the case $(w, 4w, 4w)$ by switching the indices $i, j$. In these cases $g = 1$. This leads to cases (\ref{item-two-cycle}) and (\ref{item-up4}) of Lemma \ref{lemma-genus-one}. Assuming $n > 2$ we see that the determinant $4w_iw_j - a_{ij}^2$ of the displayed matrix is $> 0$ and we conclude that $a_{ij}^2/w_iw_j < 4$. On the other hand, we know that $\text{lcm}(w_i, w_j) | a_{ij}$ and hence $a_{ij}^2/w_iw_j$ is an integer. Thus $a_{ij}^2/w_iw_j \in \{1, 2, 3\}$ and $w_i | w_j$ or vice versa. This leads to the following possibilities $$(w_1, w_2, a_{12}) = (w, w, w), (w, 2w, 2w), (w, 3w, 3w), (2w, w, 2w), \text{ or }(3w, w, 3w)$$ Observe that the case $(2w, w, 2w)$ is obtained from the case $(w, 2w, 2w)$ by switching the indices $i, j$ and similarly for the cases $(3w, w, 3w)$ and $(w, 3w, 3w)$. The first three solutions lead to cases (\ref{item-A2}), (\ref{item-B2}), and (\ref{item-G2}) of Lemma \ref{lemma-two-by-two}. In this lemma we wrote out the consequences for the integers $m_i$ and $m_j$ using that $\sum_l a_{kl}m_l = 0$ for each $k$ in particular implies $a_{ii}m_i + a_{ij}m_j \leq 0$ for $k = i$ and $a_{ij}m_i + a_{jj}m_j \leq 0$ for $k = j$. \begin{lemma} \label{lemma-two-by-two} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet }$$ If $n > 2$, then given a pair $i, j$ of $(-2)$-indices with $a_{ij} > 0$, then up to ordering we have the $m$'s, $a$'s, $w$'s \begin{enumerate} \item \label{item-A2} are given by $$\left( \begin{matrix} m_1 \\ m_2 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w \\ w & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \end{matrix} \right)$$ with $w$ arbitrary and $2m_1 \geq m_2$ and $2m_2 \geq m_1$, or \item \label{item-B2} are given by $$\left( \begin{matrix} m_1 \\ m_2 \end{matrix} \right), \quad \left( \begin{matrix} -2w & 2w \\ 2w & -4w \end{matrix} \right), \quad \left( \begin{matrix} w \\ 2w \end{matrix} \right)$$ with $w$ arbitrary and $m_1 \geq m_2$ and $2m_2 \geq m_1$, or \item \label{item-G2} are given by $$\left( \begin{matrix} m_1 \\ m_2 \end{matrix} \right), \quad \left( \begin{matrix} -2w & 3w \\ 3w & -6w \end{matrix} \right), \quad \left( \begin{matrix} w \\ 3w \end{matrix} \right)$$ with $w$ arbitrary and $2m_1 \geq 3m_2$ and $2m_2 \geq m_1$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose that $i$, $j$, and $k$ are three $(-2)$-indices with $a_{ij} > 0$ and $a_{jk} > 0$. In other words, the index $i$ meets'' $j$ and $j$ meets'' $k$. We will use without further mention that each pair $(i, j)$, $(i, k)$, and $(j, k)$ is as listed in Lemma \ref{lemma-two-by-two}. Since the matrix $A = (a_{ij})$ is semi-negative definite by Lemma \ref{lemma-recurring-symmetric-real} we see that the matrix $$\left( \begin{matrix} -2w_i & a_{ij} & a_{ik} \\ a_{ij} & -2w_j & a_{jk} \\ a_{ik} & a_{jk} & -2w_k \end{matrix} \right)$$ is negative definite unless $n = 3$. The case $n = 3$ can happen: then the determinant\footnote{It is $-8w_iw_jw_k + 2a_{ij}^2w_k + 2a_{jk}^2w_i + 2a_{ik}^2w_j + 2a_{ij}a_{jk}a_{ik}$.} of the matrix is zero and we obtain the equation $$4 = \frac{a_{ij}^2}{w_iw_j} + \frac{a_{jk}^2}{w_jw_k} + \frac{a_{ik}^2}{w_iw_k} + \frac{a_{ij}a_{ik}a_{jk}}{w_iw_jw_k}$$ of integers. The last term on the right in this equation is determined by the others because $$\left(\frac{a_{ij}a_{ik}a_{jk}}{w_iw_jw_k}\right)^2 = \frac{a_{ij}^2}{w_iw_j} \frac{a_{jk}^2}{w_jw_k} \frac{a_{ik}^2}{w_iw_k}$$ Since we have seen above that $\frac{a_{ij}^2}{w_iw_j}, \frac{a_{jk}^2}{w_jw_k}$ are in $\{1, 2, 3\}$ and $\frac{a_{ik}^2}{w_iw_k}$ in $\{0, 1, 2, 3\}$, we conclude that the only possibilities are $$(\frac{a_{ij}^2}{w_iw_j}, \frac{a_{jk}^2}{w_jw_k}, \frac{a_{ik}^2}{w_iw_k}) = (1, 1, 1), (1, 3, 0), (2, 2, 0),\text{ or } (3, 1, 0)$$ Observe that the case $(3, 1, 0)$ is obtained from the case $(1, 3, 0)$ by reversing the order the indices $i, j, k$. In each of these cases $g = 1$; the reader can find these as cases (\ref{item-three-cycle}), (\ref{item-equal-up3}), (\ref{item-equal-down3}), (\ref{item-up-up}), (\ref{item-up-down}), (\ref{item-down-up}) of Lemma \ref{lemma-genus-one} with one case corresponding to $(1, 1, 1)$, two cases corresponding to $(1, 3, 0)$, and three cases corresponding to $(2, 2, 0)$. Assuming $n > 3$ we obtain the inequality $$4 > \frac{a_{ij}^2}{w_iw_j} + \frac{a_{ik}^2}{w_iw_k} + \frac{a_{jk}^2}{w_jw_k} + \frac{a_{ij}a_{ik}a_{jk}}{w_iw_jw_k}$$ of integers. Using the restrictions on the numbers given above we see that the only possibilities are $$(\frac{a_{ij}^2}{w_iw_j}, \frac{a_{jk}^2}{w_jw_k}, \frac{a_{ik}^2}{w_iw_k}) = (1, 1, 0), (1, 2, 0),\text{ or }(2, 1, 0)$$ in particular $a_{ik} = 0$ (recall we are assuming $a_{ij} > 0$ and $a_{jk} > 0$). Observe that the case $(2, 1, 0)$ is obtained from the case $(1, 2, 0)$ by reversing the ordering of the indices $i, j, k$. The first two solutions lead to cases (\ref{item-A3}), (\ref{item-C3}), and (\ref{item-B3}) of Lemma \ref{lemma-three-by-three} where we also wrote out the consequences for the integers $m_i$, $m_j$, and $m_k$. \begin{lemma} \label{lemma-three-by-three} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet }$$ If $n > 3$, then given a triple $i, j, k$ of $(-2)$-indices with at least two $a_{ij}, a_{ik}, a_{jk}$ nonzero, then up to ordering we have the $m$'s, $a$'s, $w$'s \begin{enumerate} \item \label{item-A3} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 \\ w & -2w & w \\ 0 & w & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2$, or \item \label{item-C3} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 \\ w & -2w & 2w \\ 0 & 2w & -4w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ 2w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + 2m_3$, $2m_3 \geq m_2$, or \item \label{item-B3} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \end{matrix} \right), \quad \left( \begin{matrix} -4w & 2w & 0 \\ 2w & -4w & 2w \\ 0 & 2w & -2w \end{matrix} \right), \quad \left( \begin{matrix} 2w \\ 2w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $m_3 \geq m_2$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose that $i$, $j$, $k$, and $l$ are four $(-2)$-indices with $a_{ij} > 0$, $a_{jk} > 0$, and $a_{kl} > 0$. In other words, the index $i$ meets'' $j$, $j$ meets'' $k$, and $k$ meets'' $l$. Then we see from Lemma \ref{lemma-three-by-three} that $a_{ik} = a_{jl} = 0$. Since the matrix $A = (a_{ij})$ is semi-negative definite we see that the matrix $$\left( \begin{matrix} -2w_i & a_{ij} & 0 & a_{il} \\ a_{ij} & -2w_j & a_{jk} & 0 \\ 0 & a_{jk} & -2w_k & a_{kl} \\ a_{il} & 0 & a_{kl} & -2w_l \end{matrix} \right)$$ is negative definite unless $n = 4$. The case $n = 4$ can happen: then the determinant\footnote{It is $16w_iw_jw_kw_l - 4a_{ij}^2w_kw_l - 4a_{jk}^2w_iw_l - 4a_{kl}^2w_iw_j - 4a_{il}^2w_jw_k + a_{ij}^2a_{kl}^2 + a_{jk}^2a_{il}^2 - 2a_{ij}a_{il}a_{jk}a_{kl}$.} of the matrix is zero and we obtain the equation $$16 + \frac{a_{ij}^2}{w_iw_j}\frac{a_{kl}^2}{w_kw_l} + \frac{a_{jk}^2}{w_jw_k}\frac{a_{il}^2}{w_iw_l} = 4\frac{a_{ij}^2}{w_iw_j} + 4\frac{a_{jk}^2}{w_jw_k} + 4\frac{a_{kl}^2}{w_kw_l} + 4\frac{a_{il}^2}{w_iw_l} + 2\frac{a_{ij}a_{il}a_{jk}a_{kl}}{w_iw_jw_kw_l}$$ of nonnegative integers. The last term on the right in this equation is determined by the others because $$\left(\frac{a_{ij}a_{il}a_{jk}a_{kl}}{w_iw_jw_kw_l}\right)^2 = \frac{a_{ij}^2}{w_iw_j} \frac{a_{jk}^2}{w_jw_k} \frac{a_{kl}^2}{w_kw_l} \frac{a_{il}^2}{w_iw_l}$$ Since we have seen above that $\frac{a_{ij}^2}{w_iw_j}, \frac{a_{jk}^2}{w_jw_k}, \frac{a_{kl}^2}{w_kw_l}$ are in $\{1, 2\}$ and $\frac{a_{il}^2}{w_iw_l}$ in $\{0, 1, 2\}$, we conclude that the only possible solutions are $$(\frac{a_{ij}^2}{w_iw_j}, \frac{a_{jk}^2}{w_jw_k}, \frac{a_{kl}^2}{w_kw_l}, \frac{a_{il}^2}{w_iw_l}) = (1, 1, 1, 1) \text{ or } (2, 1, 2, 0)$$ and case $g = 1$; the reader can find these as cases (\ref{item-four-cycle}), (\ref{item-up-equal-up}), (\ref{item-up-equal-down}), and (\ref{item-down-equal-up}) of Lemma \ref{lemma-genus-one}. Assuming $n > 4$ we obtain the inequality $$16 + \frac{a_{ij}^2}{w_iw_j}\frac{a_{kl}^2}{w_kw_l} + \frac{a_{jk}^2}{w_jw_k}\frac{a_{il}^2}{w_iw_l} > 4\frac{a_{ij}^2}{w_iw_j} + 4\frac{a_{jk}^2}{w_jw_k} + 4\frac{a_{kl}^2}{w_kw_l} + 4\frac{a_{il}^2}{w_iw_l} + 2\frac{a_{ij}a_{il}a_{jk}a_{kl}}{w_iw_jw_kw_l}$$ of nonnegative integers. Using the restrictions on the numbers given above we see that the only possibilities are $$(\frac{a_{ij}^2}{w_iw_j}, \frac{a_{jk}^2}{w_jw_k}, \frac{a_{kl}^2}{w_kw_l}, \frac{a_{il}^2}{w_iw_l}) = (1, 1, 1, 0), (1, 1, 2, 0), (1, 2, 1, 0), \text{ or }(2, 1, 1, 0)$$ in particular $a_{il} = 0$ (recall that we assumed the other three to be nonzero). Observe that the case $(2, 1, 1, 0)$ is obtained from the case $(1, 1, 2, 0)$ by reversing the ordering of the indices $i, j, k, l$. The first three solutions lead to cases (\ref{item-A4}), (\ref{item-C4}), (\ref{item-B4}), and (\ref{item-F4}) of Lemma \ref{lemma-four-by-four} where we also wrote out the consequences for the integers $m_i$, $m_j$, $m_k$, and $m_l$. \begin{lemma} \label{lemma-four-by-four} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet }$$ If $n > 4$, then given four $(-2)$-indices $i, j, k, l$ with $a_{ij}, a_{jk}, a_{kl}$ nonzero, then up to ordering we have the $m$'s, $a$'s, $w$'s \begin{enumerate} \item \label{item-A4} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 \\ w & -2w & w & 0 \\ 0 & w & -2w & w \\ 0 & 0 & w & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2 + m_4$, and $2m_4 \geq m_3$, or \item \label{item-C4} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 \\ w & -2w & w & 0 \\ 0 & w & -2w & 2w \\ 0 & 0 & 2w & -4w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ 2w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2 + 2m_4$, and $2m_4 \geq m_3$, or \item \label{item-B4} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \end{matrix} \right), \quad \left( \begin{matrix} -4w & 2w & 0 & 0 \\ 2w & -4w & 2w & 0 \\ 0 & 2w & -4w & 2w \\ 0 & 0 & 2w & -2w \end{matrix} \right), \quad \left( \begin{matrix} 2w \\ 2w \\ 2w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2 + m_4$, and $m_4 \geq m_3$, or \item \label{item-F4} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 \\ w & -2w & 2w & 0 \\ 0 & 2w & -4w & 2w \\ 0 & 0 & 2w & -4w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ 2w \\ 2w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + 2m_3$, $2m_3 \geq m_2 + m_4$, and $2m_4 \geq m_3$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose that $i$, $j$, $k$, and $l$ are four $(-2)$-indices with $a_{ij} > 0$, $a_{ij} > 0$, and $a_{il} > 0$. In other words, the index $i$ meets'' the indices $j$, $k$, $l$. Then we see from Lemma \ref{lemma-three-by-three} that $a_{jk} = a_{jl} = a_{kl} = 0$. Since the matrix $A = (a_{ij})$ is semi-negative definite we see that the matrix $$\left( \begin{matrix} -2w_i & a_{ij} & a_{ik} & a_{il} \\ a_{ij} & -2w_j & 0 & 0 \\ a_{ik} & 0 & -2w_k & 0 \\ a_{il} & 0 & 0 & -2w_l \end{matrix} \right)$$ is negative definite unless $n = 4$. The case $n = 4$ can happen: then the determinant\footnote{It is $16w_iw_jw_kw_l - 4a_{ij}^2w_kw_l - 4a_{ik}^2w_jw_l - 4a_{il}^2w_jw_k$.} of the matrix is zero and we obtain the equation $$4 = \frac{a_{ij}^2}{w_iw_j} + \frac{a_{ik}^2}{w_iw_k} + \frac{a_{il}^2}{w_jw_l}$$ of nonnegative integers. Since we have seen above that $\frac{a_{ij}^2}{w_iw_j}, \frac{a_{ik}^2}{w_iw_k}, \frac{a_{il}^2}{w_iw_l}$ are in $\{1, 2\}$, we conclude that the only possibilities are up to reordering: $4 = 1 + 1 + 2$. In each of these cases $g = 1$; the reader can find these as cases (\ref{item-triple-with-up}) and (\ref{item-triple-with-down}) of Lemma \ref{lemma-genus-one}. Assuming $n > 4$ we obtain the inequality $$4 > \frac{a_{ij}^2}{w_iw_j} + \frac{a_{ik}^2}{w_iw_k} + \frac{a_{il}^2}{w_jw_l}$$ of nonnegative integers. This implies that $\frac{a_{ij}^2}{w_iw_j} = \frac{a_{ik}^2}{w_iw_k} = \frac{a_{il}^2}{w_jw_l} = 1$ and that $w_i = w_j = w_k = w_l$. This leads to case (\ref{item-D4}) of Lemma \ref{lemma-D4} where we also wrote out the consequences for the integers $m_i$, $m_j$, $m_k$, and $m_l$. \begin{lemma} \label{lemma-D4} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \\ & \bullet }$$ If $n > 4$, then given four $(-2)$-indices $i, j, k, l$ with $a_{ij}, a_{ik}, a_{il}$ nonzero, then up to ordering we have the $m$'s, $a$'s, $w$'s \begin{enumerate} \item \label{item-D4} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & w & w \\ w & -2w & 0 & 0 \\ w & 0 & -2w & 0 \\ w & 0 & 0 & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2 + m_3 + m_4$, $2m_2 \geq m_1$, $2m_3 \geq m_1$, $2m_4 \geq m_1$. Observe that this implies $m_1 \geq \max(m_2, m_3, m_4)$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose that $h$, $i$, $j$, $k$, and $l$ are five $(-2)$-indices with $a_{hi} > 0$, $a_{ij} > 0$, $a_{jk} > 0$, and $a_{kl} > 0$. In other words, the index $h$ meets'' $i$, $i$ meets'' $j$, $j$ meets'' $k$, and $k$ meets'' $l$. Then we can apply Lemmas \ref{lemma-three-by-three} and \ref{lemma-four-by-four} to see that $a_{hj} = a_{hk} = a_{ik} = a_{il} = a_{jl} = 0$ and that the fractions $\frac{a_{hi}^2}{w_hw_i}, \frac{a_{ij}^2}{w_iw_j}, \frac{a_{jk}^2}{w_jw_k}, \frac{a_{kl}^2}{w_kw_l}$ are in $\{1, 2\}$ and the fraction $\frac{a_{hl}^2}{w_hw_l} \in \{0, 1, 2\}$. Since the matrix $A = (a_{ij})$ is semi-negative definite we see that the matrix $$\left( \begin{matrix} -2w_h & a_{hi} & 0 & 0 & a_{hl} \\ a_{hi} & -2w_i & a_{ij} & 0 & 0 \\ 0 & a_{ij} & -2w_j & a_{jk} & 0 \\ 0 & 0 & a_{jk} & -2w_k & a_{kl} \\ a_{hl} & 0 & 0 & a_{kl} & -2w_l \end{matrix} \right)$$ is negative definite unless $n = 5$. The case $n = 5$ can happen: then the determinant\footnote{It is $-32w_hw_iw_jw_kw_l + 8a_{hi}^2w_jw_kw_l + 8a_{ij}^2w_hw_kw_l + 8a_{jk}^2w_hw_iw_l + 8a_{kl}^2w_hw_iw_j + 8a_{hl}^2w_iw_jw_k - 2a_{hi}^2a_{jk}^2w_l - 2a_{hi}^2a_{kl}^2w_j - 2a_{ij}^2a_{kl}^2w_h - 2a_{hl}^2a_{ij}^2w_k - 2a_{hl}^2a_{jk}^2w_i + 2a_{hi}a_{ij}a_{jk}a_{kl}a_{hl}$ .} of the matrix is zero and we obtain the equation \begin{align*} 16 + \frac{a_{hi}^2}{w_hw_i}\frac{a_{jk}^2}{w_jw_k} + \frac{a_{hi}^2}{w_hw_i}\frac{a_{kl}^2}{w_kw_l} + \frac{a_{ij}^2}{w_iw_j}\frac{a_{kl}^2}{w_kw_l} + \frac{a_{hl}^2}{w_hw_l}\frac{a_{ij}^2}{w_iw_j} + \frac{a_{hl}^2}{w_hw_l}\frac{a_{jk}^2}{w_jw_k} \\ = 4\frac{a_{hi}^2}{w_hw_i} + 4\frac{a_{ij}^2}{w_iw_j} + 4\frac{a_{jk}^2}{w_jw_k} + 4\frac{a_{kl}^2}{w_kw_l} + 4\frac{a_{hl}^2}{w_hw_l} + \frac{a_{hi}a_{ij}a_{jk}a_{kl}a_{hl}}{w_hw_iw_jw_kw_l} \end{align*} of nonnegative integers. The last term on the right in this equation is determined by the others because $$\left(\frac{a_{hi}a_{ij}a_{jk}a_{kl}a_{hl}}{w_hw_iw_jw_kw_l} \right)^2 = \frac{a_{hi}^2}{w_hw_i} \frac{a_{ij}^2}{w_iw_j} \frac{a_{jk}^2}{w_jw_k} \frac{a_{kl}^2}{w_kw_l} \frac{a_{hl}^2}{w_hw_l}$$ We conclude the only possible solutions are $$(\frac{a_{hi}^2}{w_hw_i}, \frac{a_{ij}^2}{w_iw_j}, \frac{a_{jk}^2}{w_jw_k}, \frac{a_{kl}^2}{w_kw_l}, \frac{a_{hl}^2}{w_hw_l}) = (1, 1, 1, 1, 1), (1, 1, 2, 1, 0), (1, 2, 1, 1, 0), \text{ or }(2, 1, 1, 2, 0)$$ Observe that the case $(1, 2, 1, 1, 0)$ is obtained from the case $(1, 1, 2, 1, 0)$ by reversing the order of the indices $h, i, j, k, l$. In these cases $g = 1$; the reader can find these as cases (\ref{item-five-cycle}), (\ref{item-equal-equal-up-equal}), (\ref{item-equal-equal-down-equal}), (\ref{item-up-equal-equal-up}), (\ref{item-up-equal-equal-down}), and (\ref{item-down-equal-equal-up}) of Lemma \ref{lemma-genus-one} with one case corresponding to $(1, 1, 1, 1, 1)$, two cases corresponding to $(1, 1, 2, 1, 0)$, and three cases corresponding to $(2, 1, 1, 2, 0)$. Assuming $n > 5$ we obtain the inequality \begin{align*} 16 + \frac{a_{hi}^2}{w_hw_i}\frac{a_{jk}^2}{w_jw_k} + \frac{a_{hi}^2}{w_hw_i}\frac{a_{kl}^2}{w_kw_l} + \frac{a_{ij}^2}{w_iw_j}\frac{a_{kl}^2}{w_kw_l} + \frac{a_{hl}^2}{w_hw_l}\frac{a_{ij}^2}{w_iw_j} + \frac{a_{hl}^2}{w_hw_l}\frac{a_{jk}^2}{w_jw_k} \\ > 4\frac{a_{hi}^2}{w_hw_i} + 4\frac{a_{ij}^2}{w_iw_j} + 4\frac{a_{jk}^2}{w_jw_k} + 4\frac{a_{kl}^2}{w_kw_l} + 4\frac{a_{hl}^2}{w_hw_l} + \frac{a_{hi}a_{ij}a_{jk}a_{kl}a_{hl}}{w_hw_iw_jw_kw_l} \end{align*} of nonnegative integers. Using the restrictions on the numbers given above we see that the only possibilities are $$(\frac{a_{hi}^2}{w_hw_i}, \frac{a_{ij}^2}{w_iw_j}, \frac{a_{jk}^2}{w_jw_k}, \frac{a_{kl}^2}{w_kw_l}, \frac{a_{hl}^2}{w_hw_l}) = (1, 1, 1, 1, 0), (1, 1, 1, 2, 0), \text{ or } (2, 1, 1, 1, 0)$$ in particular $a_{hl} = 0$ (recall that we assumed the other four to be nonzero). Observe that the case $(1, 1, 1, 2, 0)$ is obtained from the case $(2, 1, 1, 1, 0)$ by reversing the order of the indices $h, i, j, k, l$. The first two solutions lead to cases (\ref{item-A5}), (\ref{item-C5}), and (\ref{item-B5}) of Lemma \ref{lemma-five-by-five} where we also wrote out the consequences for the integers $m_h$, $m_i$, $m_j$, $m_k$, and $m_l$. \begin{lemma} \label{lemma-five-by-five} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet }$$ If $n > 5$, then given five $(-2)$-indices $h, i, j, k, l$ with $a_{hi}, a_{ij}, a_{jk}, a_{kl}$ nonzero, then up to ordering we have the $m$'s, $a$'s, $w$'s \begin{enumerate} \item \label{item-A5} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 & 0 \\ w & -2w & w & 0 & 0 \\ 0 & w & -2w & w & 0 \\ 0 & 0 & w & -2w & w \\ 0 & 0 & 0 & w & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2 + m_4$, $2m_4 \geq m_3 + m_5$, and $2m_5 \geq m_4$, or \item \label{item-C5} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 & 0 \\ w & -2w & w & 0 & 0 \\ 0 & w & -2w & w & 0 \\ 0 & 0 & w & -2w & 2w \\ 0 & 0 & 0 & 2w & -4w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ w \\ 2w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2 + 2m_4$, $2m_4 \geq m_3 + m_5$, and $2m_5 \geq m_4$, or \item \label{item-B5} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \end{matrix} \right), \quad \left( \begin{matrix} -4w & 2w & 0 & 0 & 0 \\ 2w & -4w & 2w & 0 & 0 \\ 0 & 2w & -4w & 2w & 0 \\ 0 & 0 & 2w & -4w & 2w \\ 0 & 0 & 0 & 2w & -2w \end{matrix} \right), \quad \left( \begin{matrix} 2w \\ 2w \\ 2w \\ 2w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2 + m_4$, $2m_4 \geq m_3 + m_5$, and $m_4 \geq m_3$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose that $h$, $i$, $j$, $k$, and $l$ are five $(-2)$-indices with $a_{hi} > 0$, $a_{hj} > 0$, $a_{hk} > 0$, and $a_{hl} > 0$. In other words, the index $h$ meets'' the indices $i$, $j$, $k$, $l$. Then we see from Lemma \ref{lemma-three-by-three} that $a_{ij} = a_{ik} = a_{il} = a_{jk} = a_{jl} = a_{kl} = 0$ and by Lemma \ref{lemma-D4} that $w_h = w_i = w_j = w_k = w_l = w$ for some integer $w > 0$ and $a_{hi} = a_{hj} = a_{hk} = a_{hl} = -2w$. The corresponding matrix $$\left( \begin{matrix} -2w & w & w & w & w \\ w & -2w & 0 & 0 & 0 \\ w & 0 & -2w & 0 & 0 \\ w & 0 & 0 & -2w & 0 \\ w & 0 & 0 & 0 & -2w \end{matrix} \right)$$ is singular. Hence this can only happen if $n = 5$ and $g = 1$. The reader can find this as case (\ref{item-quadruple}) Lemma \ref{lemma-genus-one}. \begin{lemma} \label{lemma-fourfold} Nonexistence of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[ld] \ar@{-}[r] \ar@{-}[d] & \bullet \\ \bullet & \bullet }$$ If $n > 5$, there do {\bf not} exist five $(-2)$-indices $h$, $i$, $j$, $k$ with $a_{hi} > 0$, $a_{hj} > 0$, $a_{hk} > 0$, and $a_{hl} > 0$. \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose that $h$, $i$, $j$, $k$, and $l$ are five $(-2)$-indices with $a_{hi} > 0$, $a_{ij} > 0$, $a_{jk} > 0$, and $a_{jl} > 0$. In other words, the index $h$ meets'' $i$ and the index $j$ meets'' the indices $i$, $k$, $l$. Then we see from Lemma \ref{lemma-D4} that $a_{ik} = a_{il} = a_{kl} = 0$, $w_i = w_j = w_k = w_l = w$, and $a_{ij} = a_{jk} = a_{jl} = w$ for some integer $w$. Applying Lemma \ref{lemma-four-by-four} to the four tuples $h, i, j, k$ and $h, i, j, l$ we see that $a_{hj} = a_{hk} = a_{hl} = 0$, that $w_h = \frac{1}{2}w$, $w$, or $2w$, and that correspondingly $a_{hi} = w$, $w$, or $2w$. Since $A$ is semi-negative definite we see that the matrix $$\left( \begin{matrix} -2w_h & a_{hi} & 0 & 0 & 0 \\ a_{hi} & -2w & w & 0 & 0 \\ 0 & w & -2w & w & w \\ 0 & 0 & w & -2w & 0 \\ 0 & 0 & w & 0 & -2w \end{matrix} \right)$$ is negative definite unless $n = 5$. The reader computes that the determinant of the matrix is $0$ when $w_h = \frac{1}{2}w$ or $2w$. This leads to cases (\ref{item-triple-extended-up}) and (\ref{item-triple-extended-down}) of Lemma \ref{lemma-genus-one}. For $w_h = w$ we obtain case (\ref{item-D5}) of Lemma \ref{lemma-D5}. \begin{lemma} \label{lemma-D5} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \\ & & \bullet }$$ If $n > 5$, then given five $(-2)$-indices $h, i, j, k, l$ with $a_{hi}, a_{ij}, a_{jk}, a_{jl}$ nonzero, then up to ordering we have the $m$'s, $a$'s, $w$'s \begin{enumerate} \item \label{item-D5} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 & 0 \\ w & -2w & w & 0 & 0 \\ 0 & w & -2w & w & w \\ 0 & 0 & w & -2w & 0 \\ 0 & 0 & w & 0 & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2 + m_4 + m_5$, $2m_4 \geq m_3$, and $2m_5 \geq m_3$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose that $t > 5$ and $i_1, \ldots, i_t$ are $t$ distinct $(-2)$-indices such that $a_{i_ji_{j + 1}}$ is nonzero for $j = 1, \ldots, t - 1$. We will prove by induction on $t$ that if $n = t$ this leads to possibilities (\ref{item-n-cycle}), (\ref{item-up-chain-equal-up}), (\ref{item-up-chain-equal-down}), (\ref{item-down-chain-equal-up}) of Lemma \ref{lemma-genus-one} and if $n > t$ to cases (\ref{item-An}), (\ref{item-Cn}), and (\ref{item-Bn}) of Lemma \ref{lemma-long}. First, if $a_{i_1i_t}$ is nonzero, then it is clear from the result of Lemma \ref{lemma-five-by-five} that $w_{i_1} = \ldots = w_{i_t} = w$ and that $a_{i_ji_{j + 1}} = w$ for $j = 1, \ldots, t - 1$ and $a_{i_1i_t} = w$. Then the vector $(1, \ldots, 1)$ is in the kernel of the corresponding $t \times t$ matrix. Thus we must have $n = t$ and we see that the genus is $1$ and that we are in case (\ref{item-n-cycle}) of Lemma \ref{lemma-genus-one}. Thus we may assume $a_{i_1i_t} = 0$. By induction hypothesis (or Lemma \ref{lemma-five-by-five} if $t = 6$) we see that $a_{i_ji_k} = 0$ if $k > j + 1$. Moreover, we have $w_{i_1} = \ldots = w_{i_{t - 1}} = w$ for some integer $w$ and $w_{i_1}, w_{i_t} \in \{\frac{1}{2}w, w, 2w\}$. Moreover, the value of $w_{i_1}$, resp.\ $w_{i_t}$ being $\frac{1}{2}w$, $w$, or $2w$ implies that the the value of $a_{i_1i_2}$, resp.\ $a_{i_{t - 1}i_t}$ is $w$, $w$, or $2w$. This gives $9$ possibilities. In each case it is easy to decide what happens: \begin{enumerate} \item if $(w_{i_1}, w_{i_t}) = (\frac{1}{2}w, \frac{1}{2}w)$, then we are in case (\ref{item-up-chain-equal-down}) of Lemma \ref{lemma-genus-one}, \item if $(w_{i_1}, w_{i_t}) = (\frac{1}{2}w, w)$ or $(w, \frac{1}{2}w)$ then we are in case (\ref{item-Bn}) of Lemma \ref{lemma-long}, \item if $(w_{i_1}, w_{i_t}) = (\frac{1}{2}w, 2w)$ or $(2w, \frac{1}{2}w)$ then we are in case (\ref{item-up-chain-equal-up}) of Lemma \ref{lemma-genus-one}, \item if $(w_{i_1}, w_{i_t}) = (w, w)$ then we are in case (\ref{item-An}) of Lemma \ref{lemma-long}, \item if $(w_{i_1}, w_{i_t}) = (w, 2w)$ or $(2w, w)$ then we are in case (\ref{item-Cn}) of Lemma \ref{lemma-long}, and \item if $(w_{i_1}, w_{i_t}) = (2w, 2w)$ then we are in case (\ref{item-down-chain-equal-up}) of Lemma \ref{lemma-genus-one}. \end{enumerate} \begin{lemma} \label{lemma-long} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{..}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet }$$ Let $t > 5$ and $n > t$. Then given $t$ distinct $(-2)$-indices $i_1, \ldots, i_t$ such that $a_{i_ji_{j + 1}}$ is nonzero for $j = 1, \ldots, t - 1$, then up to reversing the order of these indices we have the $a$'s and $w$'s \begin{enumerate} \item \label{item-An} are given by $w_{i_1} = w_{i_2} = \ldots = w_{i_t} = w$, $a_{i_ji_{j + 1}} = w$, and $a_{i_ji_k} = 0$ if $k > j + 1$, or \item \label{item-Cn} are given by $w_{i_1} = w_{i_2} = \ldots = w_{i_{t - 1}} = w$, $w_{j_t} = 2w$, $a_{i_ji_{j + 1}} = w$ for $j < t - 1$, $a_{i_{t - 1}i_t} = 2w$, and $a_{i_ji_k} = 0$ if $k > j + 1$, or \item \label{item-Bn} are given by $w_{i_1} = w_{i_2} = \ldots = w_{i_{t - 1}} = 2w$, $w_{j_t} = w$, $a_{i_ji_{j + 1}} = 2w$, and $a_{i_{t - 1}i_t} = 2w$, and $a_{i_ji_k} = 0$ if $k > j + 1$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose that $t > 4$ and $i_1, \ldots, i_{t + 1}$ are $t + 1$ distinct $(-2)$-indices such that $a_{i_ji_{j + 1}} > 0$ for $j = 1, \ldots, t - 1$ and such that $a_{j_{t - 1}j_{t + 1}} > 0$. See picture in Lemma \ref{lemma-Dn}. We will prove by induction on $t$ that if $n = t + 1$ this leads to possibilities (\ref{item-Dn-extended-up}) and (\ref{item-Dn-extended-down}) of Lemma \ref{lemma-genus-one} and if $n > t + 1$ to case (\ref{item-Dn}) of Lemma \ref{lemma-Dn}. By induction hypothesis (or Lemma \ref{lemma-D5} in case $t = 5$) we see that $a_{i_ji_k}$ is zero outside of the required nonvanishing ones for $j, k \geq 2$. Moreover, we see that $w_2 = \ldots = w_{t + 1} = w$ for some integer $w$ and that the nonvanishing $a_{i_ji_k}$ for $j, k \geq 2$ are equal to $w$. Applying Lemma \ref{lemma-long} (or Lemma \ref{lemma-five-by-five} if $t = 5$) to the sequence $i_1, \ldots, i_t$ and to the sequence $i_1, \ldots, i_{t - 1}, i_{t + 1}$ we conclude that $a_{i_1 i_j} = 0$ for $j \geq 3$ and that $w_1$ is equal to $\frac{1}{2}w$, $w$, or $2w$ and that correspondingly $a_{i_1i_2}$ is $w, w, 2w$. This gives $3$ possibilities. In each case it is easy to decide what happens: \begin{enumerate} \item If $w_1 = \frac{1}{2}w$, then we are in case (\ref{item-Dn-extended-down}) of Lemma \ref{lemma-genus-one}. \item If $w_1 = w$, then we are in case (\ref{item-Dn}) of Lemma \ref{lemma-Dn}. \item If $w_1 = 2w$, then we are in case (\ref{item-Dn-extended-up}) of Lemma \ref{lemma-genus-one}. \end{enumerate} \begin{lemma} \label{lemma-Dn} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{..}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \\ & & & \bullet }$$ Let $t > 4$ and $n > t + 1$. Then given $t + 1$ distinct $(-2)$-indices $i_1, \ldots, i_{t + 1}$ such that $a_{i_ji_{j + 1}}$ is nonzero for $j = 1, \ldots, t - 1$ and $a_{i_{t - 1}i_{t + 1}}$ is nonzero, then we have the $a$'s and $w$'s \begin{enumerate} \item \label{item-Dn} are given by $w_{i_1} = w_{i_2} = \ldots = w_{i_{t + 1}} = w$, $a_{i_ji_{j + 1}} = w$ for $j = 1, \ldots, t - 1$, $a_{i_{t - 1}i_{t + 1}} = w$ and $a_{i_ji_k} = 0$ for other pairs $(j, k)$ with $j > k$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose we are given $6$ distinct $(-2)$-indices $g, h, i, j, k, l$ such that $a_{gh}, a_{hi}, a_{ij}, a_{jk}, a_{il}$ are nonzero. See picture in Lemma \ref{lemma-E6}. Then we can apply Lemma \ref{lemma-D5} to see that we must be in the situation of Lemma \ref{lemma-E6}. Since the determinant is $3w^6 > 0$ we conclude that in this case it never happens that $n = 6$! \begin{lemma} \label{lemma-E6} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \ar@{-}[r] & \bullet \\ & & \bullet }$$ Let $n > 6$. Then given $6$ distinct $(-2)$-indices $i_1, \ldots, i_6$ such that $a_{12}, a_{23}, a_{34}, a_{45}, a_{36}$ are nonzero, then we have the $m$'s, $a$'s, and $w$'s \begin{enumerate} \item \label{item-E6} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ m_6 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 & 0 & 0 \\ w & -2w & w & 0 & 0 & 0 \\ 0 & w & -2w & w & 0 & w \\ 0 & 0 & w & -2w & w & 0 \\ 0 & 0 & 0 & w & -2w & 0 \\ 0 & 0 & w & 0 & 0 & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ w \\ w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2 + m_4 + m_6$, $2m_4 \geq m_3 + m_5$, $2m_5 \geq m_3$, and $2m_6 \geq m_3$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose that $t \geq 4$ and $i_0, \ldots, i_{t + 1}$ are $t + 2$ distinct $(-2)$-indices such that $a_{i_ji_{j + 1}} > 0$ for $j = 1, \ldots, t - 1$ and $a_{i_0i_2} > 0$ and $a_{i_{t - 1}i_{t + 1}} > 0$. See picture in Lemma \ref{lemma-double-triple}. Then we can apply Lemmas \ref{lemma-D5} and \ref{lemma-Dn} to see that all other $a_{i_ji_k}$ for $j < k$ are zero and that $w_{i_0} = \ldots = w_{i_{t + 1}} = w$ for some integer $w$ and that the required nonzero off diagonal entries of $A$ are equal to $w$. A computation shows that the determinant of the corresponding matrix is zero. Hence $n = t + 2$ and we are in case (\ref{item-double-triple}) of Lemma \ref{lemma-genus-one}. \begin{lemma} \label{lemma-double-triple} Nonexistence of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{..}[r] \ar@{-}[d] & \bullet \ar@{-}[d] \ar@{-}[r] & \bullet \\ & \bullet & \bullet }$$ Assume $t \geq 4$ and $n > t + 2$. There do {\bf not} exist $t + 2$ distinct $(-2)$-indices $i_0, \ldots, i_{t + 1}$ such that $a_{i_ji_{j + 1}} > 0$ for $j = 1, \ldots, t - 1$ and $a_{i_0i_2} > 0$ and $a_{i_{t - 1}i_{t + 1}} > 0$. \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose we are given $7$ distinct $(-2)$-indices $f, g, h, i, j, k, l$ such that the numbers $a_{fg}, a_{gh}, a_{ij}, a_{jh}, a_{kl}, a_{lh}$ are nonzero. See picture in Lemma \ref{lemma-E6-completed}. Then we can apply Lemma \ref{lemma-D5} to see that the corresponding matrix is $$\left( \begin{matrix} -2w & w & 0 & 0 & 0 & 0 & 0 \\ w & -2w & w & 0 & 0 & 0 & 0 \\ 0 & w & -2w & 0 & w & 0 & w \\ 0 & 0 & 0 & -2w & w & 0 & 0 \\ 0 & 0 & w & w & -2w & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -2w & w \\ 0 & 0 & w & 0 & 0 & w & -2w \end{matrix} \right)$$ Since the determinant is $0$ we conclude that we must have $n = 7$ and $g = 1$ and we get case (\ref{item-E6-completed}) of Lemma \ref{lemma-genus-one}. \begin{lemma} \label{lemma-E6-completed} Nonexistence of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \ar@{-}[r] & \bullet \\ & & \bullet \ar@{-}[d] \\ & & \bullet }$$ Assume $n > 7$. There do {\bf not} exist $7$ distinct $(-2)$-indices $f, g, h, i, j, k, l$ such that $a_{fg}, a_{gh}, a_{ij}, a_{jh}, a_{kl}, a_{lh}$ are nonzero. \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose we are given $7$ distinct $(-2)$-indices $f, g, h, i, j, k, l$ such that the numbers $a_{fg}, a_{gh}, a_{hi}, a_{ij}, a_{jk}, a_{il}$ are nonzero. See picture in Lemma \ref{lemma-E7}. Then we can apply Lemmas \ref{lemma-D5} and \ref{lemma-Dn} to see that we must be in the situation of Lemma \ref{lemma-E7}. Since the determinant is $-8w^7 > 0$ we conclude that in this case it never happens that $n = 7$! \begin{lemma} \label{lemma-E7} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \ar@{-}[r] & \bullet \\ & & & \bullet }$$ Let $n > 7$. Then given $7$ distinct $(-2)$-indices $i_1, \ldots, i_7$ such that $a_{12}, a_{23}, a_{34}, a_{45}, a_{56}, a_{47}$ are nonzero, then we have the $m$'s, $a$'s, and $w$'s \begin{enumerate} \item \label{item-E7} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ m_6 \\ m_7 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 & 0 & 0 & 0 \\ w & -2w & w & 0 & 0 & 0 & 0 \\ 0 & w & -2w & w & 0 & 0 & 0 \\ 0 & 0 & w & -2w & w & 0 & w \\ 0 & 0 & 0 & w & -2w & w & 0 \\ 0 & 0 & 0 & 0 & w & -2w & 0 \\ 0 & 0 & 0 & w & 0 & 0 & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ w \\ w \\ w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2 + m_4$, $2m_4 \geq m_3 + m_5 + m_7$, $2m_5 \geq m_4 + m_6$, $2m_6 \geq m_5$, and $2m_7 \geq m_4$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose we are given $8$ distinct $(-2)$-indices whose pattern of nonzero entries $a_{ij}$ of the matrix $A$ looks like $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \ar@{-}[r] & \bullet \\ & & & & \bullet }$$ or like $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \\ & & & \bullet }$$ Arguing exactly as in the proof of Lemma \ref{lemma-E7} we see that the first pattern leads to case (\ref{item-E8}) in Lemma \ref{lemma-E8} and does not lead to a new case in Lemma \ref{lemma-genus-one}. Arguing exactly as in the proof of Lemma \ref{lemma-E6-completed} we see that the second pattern does not occur if $n > 8$, but leads to case (\ref{item-E7-completed}) in Lemma \ref{lemma-genus-one}. \begin{lemma} \label{lemma-E8} Classification of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \ar@{-}[r] & \bullet \\ & & & & \bullet }$$ Let $n > 8$. Then given $8$ distinct $(-2)$-indices $i_1, \ldots, i_8$ such that $a_{12}, a_{23}, a_{34}, a_{45}, a_{56}, a_{65}, a_{57}$ are nonzero, then we have the $m$'s, $a$'s, and $w$'s \begin{enumerate} \item \label{item-E8} are given by $$\left( \begin{matrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ m_6 \\ m_7 \\ m_8 \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 & 0 & 0 & 0 & 0 \\ w & -2w & w & 0 & 0 & 0 & 0 & 0 \\ 0 & w & -2w & w & 0 & 0 & 0 & 0 \\ 0 & 0 & w & -2w & w & 0 & 0 & 0 \\ 0 & 0 & 0 & w & -2w & w & 0 & w \\ 0 & 0 & 0 & 0 & w & -2w & w & 0 \\ 0 & 0 & 0 & 0 & 0 & w & -2w & 0 \\ 0 & 0 & 0 & 0 & w & 0 & 0 & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ w \\ w \\ w \\ w \\ w \end{matrix} \right)$$ with $2m_1 \geq m_2$, $2m_2 \geq m_1 + m_3$, $2m_3 \geq m_2 + m_4$, $2m_4 \geq m_3 + m_5$, $2m_5 \geq m_4 + m_6 + m_8$, $2m_6 \geq m_5 + m_7$, $2m_7 \geq m_6$, and $2m_8 \geq m_5$. \end{enumerate} \end{lemma} \begin{proof} See discussion above. \end{proof} \begin{lemma} \label{lemma-E7-completed} Nonexistence of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \\ & & & \bullet }$$ Assume $n > 8$. There do {\bf not} exist $8$ distinct $(-2)$-indices $e, f, g, h, i, j, k, l$ such that $a_{ef}, a_{fg}, a_{gh}, a_{hi}, a_{ij}, a_{jk}, a_{lh}$ are nonzero. \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Suppose we are given $9$ distinct $(-2)$-indices whose pattern of nonzero entries $a_{ij}$ of the matrix $A$ looks like $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \ar@{-}[r] & \bullet \\ & & & & & \bullet }$$ Arguing exactly as in the proof of Lemma \ref{lemma-E6-completed} we see that this pattern does not occur if $n > 9$, but leads to case (\ref{item-E8-completed}) in Lemma \ref{lemma-genus-one}. \begin{lemma} \label{lemma-E8-completed} Nonexistence of proper subgraphs of the form $$\xymatrix{ \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] & \bullet \ar@{-}[r] \ar@{-}[d] & \bullet \ar@{-}[r] & \bullet \\ & & & & & \bullet }$$ Assume $n > 9$. There do {\bf not} exist $9$ distinct $(-2)$-indices $d, e, f, g, h, i, j, k, l$ such that $a_{de}, a_{ef}, a_{fg}, a_{gh}, a_{hi}, a_{ij}, a_{jk}, a_{lh}$ are nonzero. \end{lemma} \begin{proof} See discussion above. \end{proof} \noindent Collecting all the information together we find the following. \begin{proposition} \label{proposition-classify-subgraphs} Let $n, m_i, a_{ij}, w_i, g_i$ be a numerical type of genus $g$. Let $I \subset \{1, \ldots, n\}$ be a subset of cardinality $\geq 2$ consisting of $(-2)$-indices such that there does not exist a nonempty proper subset $I' \subset I$ with $a_{i'i} = 0$ for $i' \in I$, $i \in I \setminus I'$. Then up to reordering the $m_i$'s, $a_{ij}$'s, $w_i$'s for $i, j \in I$ are as listed in Lemmas \ref{lemma-two-by-two}, \ref{lemma-three-by-three}, \ref{lemma-four-by-four}, \ref{lemma-D4}, \ref{lemma-five-by-five}, \ref{lemma-D5}, \ref{lemma-long}, \ref{lemma-Dn}, \ref{lemma-E6}, \ref{lemma-E7}, or \ref{lemma-E8}. \end{proposition} \begin{proof} This follows from the discussion above; see discussion at the start of Section \ref{section-classify-proper-subgraphs}. \end{proof} \section{Classification of minimal type for genus zero and one} \label{section-classification-genus-one} \noindent The title of the section explains it all. \begin{lemma}[Genus zero] \label{lemma-genus-zero} The only minimal numerical type of genus zero is $n = 1$, $m_1 = 1$, $a_{11} = 0$, $w_1 = 1$, $g_1 = 0$. \end{lemma} \begin{proof} Follows from Lemmas \ref{lemma-non-irreducible-minimal-type-genus-at-least-one} and \ref{lemma-irreducible}. \end{proof} \begin{lemma}[Genus one] \label{lemma-genus-one} The minimal numerical types of genus one are up to equivalence \begin{enumerate} \item \label{item-one} $n = 1$, $a_{11} = 0$, $g_1 = 1$, $m_1, w_1 \geq 1$ arbitrary, \item \label{item-two-cycle} $n = 2$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & 2w \\ 2w & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-up4} $n = 2$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} 2m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & 4w \\ 4w & -8w \end{matrix} \right), \quad \left( \begin{matrix} w \\ 4w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-three-cycle} $n = 3$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & w \\ w & -2w & w \\ w & w & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-equal-up3} $n = 3$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ 2m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 \\ w & -2w & 3w \\ 0 & 3w & -6w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ 3w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-equal-down3} $n = 3$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ 2m \\ 3m \end{matrix} \right), \quad \left( \begin{matrix} -6w & 3w & 0 \\ 3w & -6w & 3w \\ 0 & 3w & -2w \end{matrix} \right), \quad \left( \begin{matrix} 3w \\ 3w \\ w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-up-up} $n = 3$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} 2m \\ 2m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & 2w & 0 \\ 2w & -4w & 4w \\ 0 & 4w & -8w \end{matrix} \right), \quad \left( \begin{matrix} w \\ 2w \\ 4w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-up-down} $n = 3$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & 2w & 0 \\ 2w & -4w & 2w \\ 0 & 2w & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ 2w \\ w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-down-up} $n = 3$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ 2m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -4w & 2w & 0 \\ 2w & -2w & 2w \\ 0 & 2w & -4w \end{matrix} \right), \quad \left( \begin{matrix} 2w \\ w \\ 2w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-four-cycle} $n = 4$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ m \\ m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & w \\ w & -2w & w & 0 \\ 0 & w & -2w & w \\ w & 0 & w & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-up-equal-up} $n = 4$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} 2m \\ 2m \\ 2m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & 2w & 0 & 0 \\ 2w & -4w & 2w & 0 \\ 0 & 2w & -4w & 4w \\ 0 & 0 & 4w & -8w \end{matrix} \right), \quad \left( \begin{matrix} w \\ 2w \\ 2w \\ 4w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-up-equal-down} $n = 4$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ m \\ m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & 2w & 0 & 0 \\ 2w & -4w & 2w & 0 \\ 0 & 2w & -4w & 2w \\ 0 & 0 & 2w & -2w \end{matrix} \right), \quad \left( \begin{matrix} w \\ 2w \\ 2w \\ w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-down-equal-up} $n = 4$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ 2m \\ 2m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -4w & 2w & 0 & 0 \\ 2w & -2w & w & 0 \\ 0 & w & -2w & 2w \\ 0 & 0 & 2w & -4w \end{matrix} \right), \quad \left( \begin{matrix} 2w \\ w \\ w \\ 2w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-triple-with-up} $n = 4$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} 2m \\ m \\ m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & w & 2w \\ w & -2w & 0 & 0 \\ w & 0 & -2w & 0 \\ 2w & 0 & 0 & -4w \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ 2w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-triple-with-down} $n = 4$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} 2m \\ m \\ m \\ 2m \end{matrix} \right), \quad \left( \begin{matrix} -4w & 2w & 2w & 2w \\ 2w & -4w & 0 & 0 \\ 2w & 0 & -4w & 0 \\ 2w & 0 & 0 & -2w \end{matrix} \right), \quad \left( \begin{matrix} 2w \\ 2w \\ 2w \\ w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-five-cycle} $n = 5$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ m \\ m \\ m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 & w \\ w & -2w & w & 0 & 0 \\ 0 & w & -2w & w & 0 \\ 0 & 0 & w & -2w & w \\ w & 0 & 0 & w & -2w \\ \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ w \\ w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-equal-equal-up-equal} $n = 5$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ 2m \\ 3m \\ 2m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & w & 0 & 0 & 0 \\ w & -2w & w & 0 & 0 \\ 0 & w & -2w & 2w & 0 \\ 0 & 0 & 2w & -4w & 2w \\ 0 & 0 & 0 & 2w & -4w \\ \end{matrix} \right), \quad \left( \begin{matrix} w \\ w \\ w \\ 2w \\ 2w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-equal-equal-down-equal} $n = 5$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ 2m \\ 3m \\ 4m \\ 2m \end{matrix} \right), \quad \left( \begin{matrix} -4w & 2w & 0 & 0 & 0 \\ 2w & -4w & 2w & 0 & 0 \\ 0 & 2w & -4w & 2w & 0 \\ 0 & 0 & 2w & -2w & w \\ 0 & 0 & 0 & w & -2w \\ \end{matrix} \right), \quad \left( \begin{matrix} 2w \\ 2w \\ 2w \\ w \\ w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-up-equal-equal-up} $n = 5$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} 2m \\ 2m \\ 2m \\ 2m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & 2w & 0 & 0 & 0 \\ 2w & -4w & 2w & 0 & 0 \\ 0 & 2w & -4w & 2w & 0 \\ 0 & 0 & 2w & -4w & 4w \\ 0 & 0 & 0 & 4w & -8w \\ \end{matrix} \right), \quad \left( \begin{matrix} w \\ 2w \\ 2w \\ 2w \\ 4w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-up-equal-equal-down} $n = 5$, and $m_i, a_{ij}, w_i, g_i$ given by $$\left( \begin{matrix} m \\ m \\ m \\ m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -2w & 2w & 0 & 0 & 0 \\ 2w & -4w & 2w & 0 & 0 \\ 0 & 2w & -4w & 2w & 0 \\ 0 & 0 & 2w & -4w & 2w \\ 0 & 0 & 0 & 2w & -2w \\ \end{matrix} \right), \quad \left( \begin{matrix} w \\ 2w \\ 2w \\ 2w \\ w \end{matrix} \right), \quad \left( \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix} \right)$$ with $w$ and $m$ arbitrary, \item \label{item-down-equal-equal-up} $n = 5$, and $m_i, a_{ij}, w_i, g_i$ given by  \left( \begin{matrix} m \\ 2m \\ 2m \\ 2m \\ m \end{matrix} \right), \quad \left( \begin{matrix} -4w & 2w & 0 & 0 & 0 \\ 2w & -2w & w & 0 & 0 \\ 0 & w & -2w & w & 0 \\ 0 & 0 & w & -2w & 2w \\ 0 & 0