Connected fiber graphs with negative semidefinite intersection form

A proper induced subgraph cannot have a nonzero null vector. Its principal matrix is negative semidefinite by [F1]. Extending a null vector by zero gives a vector $x$ with $x^{\mathsf{T}}Mx=0$, hence $Mx=0$. Since $\ker M$ is generated by a strictly positive vector, this extended vector cannot vanish at any vertex; therefore the subgraph was all of $G$.

No edge has multiplicity at least three: on its two endpoints the principal matrix $\left(\begin{array}{cc}-2& b\\ b& -2\end{array}\right)$ has positive eigenvalue $b-2$ when $b\ge 3$. If an edge has multiplicity two, $(1,1)$ is a nonzero null vector of its principal matrix, so [step 1.1] forces that two-vertex graph to be all of $G$; this is ${\tilde{A}}_1$. Henceforth every edge is simple.

If a vertex has degree $d\ge 5$, the principal star matrix has positive quadratic value at the vector with center $\sqrt{d}$ and each leaf $1$: the value is $-4d+2d\sqrt{d}>0$, contradicting [F1]. If a vertex has degree four, the star vector with center $2$ and leaves $1$ is null, so [step 1.1] forces the entire graph to be that star, ${\tilde{D}}_4$. Otherwise the maximum degree is at most three.

By steps 2.1 and 2.2 the graph is simple with maximum degree at most three. If it contains a cycle, choose a shortest simple cycle; it has no chord, since any chord would cut it into a shorter cycle. The vector equal to one on this induced cycle and zero elsewhere has quadratic value zero: each cycle vertex has exactly two selected incident edges and the cycle has no chords. By [step 1.1] its vertex set is all of $G$, hence $G={\tilde{A}}_n$ for its number of vertices $n+1$. If $G$ is a tree with no vertex of degree three, it is a path; for a path on $r\ge 1$ vertices, $-x^{\mathsf{T}}Mx=x_1^2+x_r^2+{\sum }_{i=1}^{r-1}(x_i-x_{i+1}{)}^2>0$ for every nonzero $x$, so it has no kernel.

If the tree has at least two trivalent vertices, take two consecutive trivalent vertices and the path between them, together with one adjacent off-path vertex at each of the two unused branches at both ends. This subgraph is an affine ${\tilde{D}}_n$ graph. Its positive null vector has value $2$ on the path and the two trivalent vertices and value $1$ on the four leaves; the row equations give $M_{H}m=0$, and the edge-square identity $x^{\mathsf{T}}{M}_{H}x=-{\sum }_{i<j}{b}_{ij}(\sqrt{m_j\mathrm{/}{m}_i}{x}_i-\sqrt{m_i\mathrm{/}{m}_j}{x}_j{)}^2$ shows it is negative semidefinite with one-dimensional kernel. Thus [step 1.1] forces $G=H$, giving ${\tilde{D}}_n$.

By steps 2.1–2.2, 3.1, and 4.1, the only remaining case is a tree with exactly one trivalent vertex. Let its three arm lengths, counted in vertices beyond the central vertex, be $1\le p\le q\le s$. For $A=-M$, each arm block is the positive definite path matrix with diagonal $2$ and adjacent entries $-1$. Solving the path equations gives the endpoint entry of its inverse as $p\mathrm{/}(p+1)$ (the solution of $A_{p}u=e_1$ is $u_j=(p+1-j)\mathrm{/}(p+1)$). Eliminating the three arm blocks leaves central Schur complement $2-p\mathrm{/}(p+1)-q\mathrm{/}(q+1)-s\mathrm{/}(s+1)$. Since $A$ is positive semidefinite of corank one, this complement is zero, so $1\mathrm{/}(p+1)+1\mathrm{/}(q+1)+1\mathrm{/}(s+1)=1$.

If $p\ge 2$, each reciprocal is at most $1\mathrm{/}3$; equality of their sum with $1$ forces $(p,q,s)=(2,2,2)$, the affine $E_6$ graph. If $p=1$, then $1\mathrm{/}(q+1)+1\mathrm{/}(s+1)=1\mathrm{/}2$. With $q\le s$, $q=2$ gives $s=5$ and $q=3$ gives $s=3$; $q=1$ would require $1\mathrm{/}(s+1)=0$, while $q\ge 4$ makes the sum at most $2\mathrm{/}5$. These are exactly the affine $E_8$ and $E_7$ graphs. This exhausts the single-trivalent-vertex case.

The integer matrix $M$ has a one-dimensional real kernel, so its rational nullspace is also one-dimensional because rank is unchanged on extending scalars from $\mathbb{Q}$ to $\mathbb{R}$. It therefore has a nonzero rational kernel vector; clearing denominators and choosing its sign gives an integral vector proportional to the strictly positive vector in the hypothesis. The one-dimensional kernel makes this positive integral vector unique up to positive integer scale, and dividing its coordinates by their greatest common divisor gives the unique primitive positive integral kernel vector. The classification in steps 3.1–6.1 includes the double-edge ${\tilde{A}}_1$, the four-legged ${\tilde{D}}_4$, and all three exceptional arm triples.