Extremal state counts for virtual knot diagrams

FPRD Lab research note, 18 September 2026

Status: Complete proposed proof, with exhaustive internal computational checks. Not independently reviewed, not proof-assistant verified, and no claim of priority.

1. The question and answer

Problem 8.1 in T. Ohtsuki (ed.), Problems on Low-dimensional Topology, 2014, pp. 11-12, asks for all virtual knot diagrams attaining the stated upper bounds for the numbers of one-, two-, and three-circle smoothing states. These are counts for a fixed diagram, not minima over all diagrams representing its virtual knot.

Let D have r real crossings. Its linked-chord graph G(D) has one vertex for each chord of the Gauss diagram and an edge exactly when the endpoints of two chords alternate around its circle. Crossing signs and chord arrows are ignored here. A free chord is an isolated vertex.

Write P_m for the path on m vertices, with P_0 the empty graph; C_m is the simple cycle on m vertices, defined for m >= 3; I is a single isolated vertex; and disjoint union is denoted by the symbol below.

Proposed classification theorem

For every virtual knot diagram D:

$$s_1(D)=\frac{2^{r+1}-(-1)^{r+1}}3 \quad\Longleftrightarrow\quad G(D)\cong P_r.$$

For r >= 1,

$$s_2(D)=2^{r-1} \quad\Longleftrightarrow\quad G(D)\cong P_{r-1}\sqcup I\quad\text{or}\quad G(D)\cong C_r.$$

The cycle alternative in this line requires r >= 3. For r >= 3,

$$s_3(D)=3\cdot2^{r-3} \quad\Longleftrightarrow\quad G(D)\cong P_{r-3}\sqcup3I\quad\text{or}\quad G(D)\cong C_{r-2}\sqcup2I.$$

The cycle alternative in this line requires r >= 5. For r = 0, 1, 2 the proposed three-state upper-bound value is nonintegral, so equality is impossible. In particular, the small three-state equality cases r = 3 and r = 4 are the edgeless graphs on three and four vertices.

These conditions classify all Gauss diagrams having the specified linked-chord graphs. They do not require a particular planar drawing, a particular ordering among mutually unlinked chords, or a chosen sign/arrow assignment. In the source’s Figure 6 on page 12, F_r has linked-chord graph P_r and F’_r has linked-chord graph C_r. The source supplies extremal examples; the claim proved below is that no other linked-chord graphs are extremal.

2. The standard circuit-nullity input

For a finite simple graph G on n vertices with adjacency matrix A over the two-element field, define

$$F_G(x)=\sum_{d\in\mathbb F_2^n} x^{\nu(A+\operatorname{diag}d)}, \qquad c_j(G)=[x^j]F_G(x),$$

where nu is nullity over the two-element field. This is a sum over all diagonal assignments to the full matrix, not the usual sum over induced submatrices in the vertex-nullity interlace polynomial.

For a virtual knot diagram with at least one real crossing, the original traversal is an Euler circuit in the connected four-regular graph whose vertices are its real crossings. Virtual crossings do not join strands in this graph. At every real crossing, neither smoothing follows the original through-crossing pairing: one is the other orientation-consistent transition and the other is the orientation-inconsistent transition. By the extended Cohn-Lempel equality, these correspond respectively to diagonal entries zero and one, without deleting a row. The number of state circles is

$$1+\nu(A(G(D))+\operatorname{diag}d).$$

Consequently

$$s_k(D)=c_{k-1}(G(D)). \tag{1}$$

For zero real crossings the formula holds directly, with one state consisting of one circle.

External input: Lorenzo Traldi, Binary nullity, Euler circuits and interlace polynomials, arXiv:0903.4405, Theorem 4 and the preceding definition on PDF page 4. This is a known theorem, not an FPRD result. Its statement explicitly permits arbitrary undirected four-regular graphs, not only planar graphs. The rest of the proof below is a finite-simple-graph argument.

3. A positive three-term recursion

Let vw be an edge of G, let R = V(G) minus {v,w}, and write b and c for the adjacency vectors from v and w into R. Let B be the adjacency matrix induced on R. Let

$$L_v=(G*v)-v,$$

where G*v toggles every edge between two different neighbors of v, and changes no other edge.

For t = 0,1 let H_t be the simple graph on R whose off-diagonal adjacency is

$$(A(H_t))_{ij}=B_{ij}+t b_i b_j+b_i c_j+c_i b_j, \qquad i\ne j, \tag{2}$$

with all additions in the two-element field. Then

$$F_G=F_{L_v}+F_{H_0}+F_{H_1}. \tag{3}$$

Proof. Partition the diagonal assignments according to d_v. If d_v = 1, the one-by-one pivot at v gives the Schur complement A(G-v) plus the outer product of the adjacency vector at v with itself. Off its diagonal this is local complementation; diagonal changes simply permute the freely chosen remaining diagonals. This contributes F_{L_v}.

If d_v = 0, put d_w = t. The block at v,w is invertible:

$$\begin{pmatrix}0&1\\1&t\end{pmatrix}^{-1} =\begin{pmatrix}t&1\\1&0\end{pmatrix}.$$

Its Schur complement on R is

$$B+\operatorname{diag}d_R+tbb^T+bc^T+cb^T.$$

Eliminating an invertible block preserves nullity. Its off-diagonal entries are (2), and again its diagonal correction only reparametrizes the free diagonal. The two choices of t give the other two summands. All coefficients in all three summands are nonnegative integers. This proves (3).

Two other identities will be useful:

$$F_{G\sqcup H}=F_GF_H,\qquad F_{nI}=(1+x)^n, \tag{4}$$

$$F_G(1)=2^n,\qquad F_G(-2)=(-1)^n. \tag{5}$$

The first assertions follow from block-diagonal matrices. The last assertion follows by induction using (3), since the orders of its three graphs are n-1,n-2,n-2; the edgeless case follows from (4).

4. Bounds for all finite simple graphs

Put

$$U_n=\frac{2^{n+1}-(-1)^{n+1}}3,\quad B_n=2^{n-1}\ (n\ge1),\quad C_n=3\cdot2^{n-3}\ (n\ge3).$$

Then every simple graph G on n vertices satisfies

$$c_0(G)\le U_n;\qquad c_1(G)\le B_n\ (n\ge1);\qquad c_2(G)\le C_n\ (n\ge3). \tag{6}$$

For c_0, use U_0 = U_1 = 1 and U_n = U_{n-1}+2U_{n-2} in (3). Edgeless graphs have c_0 = 1.

For c_1, the values for orders zero, one, and two are directly bounded by 0,1,2. A two-vertex graph with an edge has c_1 = 1. For n >= 3, the three bounds in (3) sum to B_n. An edgeless graph has c_1 = n <= 2^{n-1}, with equality only at n = 1,2.

For c_2, the maxima on orders zero, one, and two are 0,0,1. A three-vertex graph with an edge has c_2 <= 1, strictly below C_3 = 3. A four-vertex graph with an edge has c_2 <= 3+2 = 5, strictly below C_4 = 6. For n >= 5 the three bounds in (3) sum to C_n. Edgeless graphs have c_2 = binomial(n,2), which is at most C_n, with equality exactly at n = 3,4. For example, the ratio binomial(n,2)/2^n strictly decreases from n = 4 onward.

Whenever an equality in (6) occurs and the corresponding bounds add exactly in (3), every branch in (3) must itself be an equality graph. In particular, we may draw the appropriate conclusion about L_v for every nonisolated vertex v, not merely for one selected edge.

5. Two elementary local-complementation observations

Degree observation. If L_v has maximum degree at most two for every nonisolated vertex v of a graph without isolated vertices, then any vertex u of degree at least three is universal. Indeed, if v were a nonneighbor of u, neither local complementation at v nor deletion of v would change the degree of u.

The same argument applies inside a graph H without isolated vertices when fixed isolated vertices have been added outside H.

True-twin observation. Suppose H has no isolated vertices. For u != v, u is isolated in L_v(H) if and only if

$$N_H[u]=N_H[v]. \tag{7}$$

To see this, a nonneighbor u of v keeps all its original neighbors and cannot become isolated. For a neighbor u of v, becoming isolated after toggling the edges among N(v) and deleting v means that u was adjacent to every other neighbor of v, and to no vertex outside N[v]. This is exactly (7).

True-twin equality is an equivalence relation. Its classes are cliques. Thus the number of isolated vertices in L_v(H) is the size of the true-twin class of v minus one.

6. Equality for c_0: only a path

We prove by induction that c_0(G) = U_n if and only if G = P_n.

The assertion is direct for n = 0,1. For n >= 2, an isolated vertex gives c_0(G) = c_0(G-v) <= U_{n-1} < U_n. Hence an equality graph has no isolated vertices. By (3), induction forces L_v = P_{n-1} for every v.

The degree observation shows that any vertex of degree at least three must be universal. Suppose u is universal. Then

$$L_u=\overline{G-u}=P_{n-1}.$$

For n >= 5, an endpoint a of this path has degree n-2 in G: it is a nonuniversal vertex of degree at least three, a contradiction. At n = 4 the only resulting graph is a triangle with a pendant vertex; deleting that pendant vertex gives a triangle, not P_3. There is no degree-three vertex at smaller orders.

Thus G has maximum degree at most two. If G were disconnected, every component would contain at least two vertices, and L_v would still have at least two nonempty components, contrary to being a path. Hence G is a path or a cycle. Local complementation and deletion in a cycle produce C_{n-1} for n >= 4, and two isolated vertices for n = 3. Neither is the required path. Therefore G = P_n.

Conversely, applying (3) at an endpoint of P_n gives

$$F_{P_n}=F_{P_{n-1}}+2F_{P_{n-2}}\quad(n\ge2),$$

with F_{P_0} = 1 and F_{P_1} = 1+x. Therefore

$$F_{P_n}(x)=U_n+V_nx, \qquad V_n=\frac{2^n-(-1)^n}{3}. \tag{8}$$

In particular, paths attain the c_0 bound.

7. Equality for c_1: a cycle or a path plus one isolate

Suppose first that G has an isolated vertex and write G = I disjoint H, with m = n-1. Then

$$c_1(G)=c_0(H)+c_1(H)\le F_H(1)=2^m.$$

Equality means F_H has degree at most one. Equations (5) then determine its constant coefficient to be U_m. Section 6 forces H = P_m. Conversely, (8) proves equality for I disjoint P_m.

We now consider graphs without isolated vertices. The small orders are immediate; for n >= 3 equality in (3) forces each L_v to be either C_{n-1} or I disjoint P_{n-2}. Both kinds have maximum degree at most two. If u has degree at least three, it is universal. We exclude its two possible local-deletion graphs.

If L_u = I disjoint P_{n-2}, an endpoint of the path has degree n-2 in G. This contradicts the degree observation for n >= 5. For n = 4 the graph is the diamond K_4 minus an edge. Local complementation and deletion at a degree-two vertex of the diamond produce P_3, which is not a c_1 equality graph.

If L_u = C_{n-1}, every other vertex has degree n-3 in G, contradicting the degree observation for n >= 6. At n = 4 the graph is the three-leaf star, and deleting a leaf gives P_3. At n = 5 the graph is two triangles meeting at their common universal vertex; local complementation and deletion at a nonuniversal vertex give C_3 disjoint I, which is not a c_1 equality graph on four vertices.

Thus G has maximum degree at most two. Its components are paths of size at least two and cycles. In the connected case, a path has c_1 = V_n < 2^{n-1} for n >= 2, leaving only cycles.

If G is disconnected and one component has size at least three, choose an endpoint in a path component, or any vertex in a cycle component. Except for a triangle, L_v contains two nontrivial components; a triangle instead contributes two isolated vertices and leaves another component. Neither configuration is allowed. Consequently all components must be edges. Local complementation and deletion give one isolate together with the remaining edges, which fits the required form only when G is exactly two disjoint edges. But

$$F_{2P_2}=(3+x)^2,\qquad c_1(2P_2)=6<8.$$

This eliminates the disconnected case without isolates.

It remains to confirm that cycles attain the bound. Direct calculation gives

$$F_{C_3}=3+4x+x^2, \qquad F_{C_4}=5+8x+3x^2.$$

For n >= 5, (3) along an edge of a cycle has branches C_{n-1},C_{n-2},C_{n-2}. Together with (8), these base cases show

$$F_{C_n}(x)=(1+x)F_{P_{n-1}}(x)\quad(n\ge3). \tag{9}$$

Its coefficient of x is U_{n-1}+V_{n-1}=2^{n-1}. Thus the c_1 classification is complete. Notice also that every c_1 equality graph has polynomial degree at most two.

8. Equality for c_2: exactly the stated two families

For n = 3,4, Section 4 already proves that only edgeless graphs attain the bound. Induct on n >= 5.

8.1 Graphs with at least two isolated vertices

Write G = 2I disjoint H, with m = n-2 >= 3. From (4),

$$\begin{aligned} c_2(G)&=c_0(H)+2c_1(H)+c_2(H)\\ &=2^m+c_1(H)-\sum_{j\ge3}c_j(H)\\ &\le 2^m+2^{m-1}=3\cdot2^{n-3}. \end{aligned} \tag{10}$$

Equality is equivalent to c_1(H) = 2^{m-1} and no coefficients above degree two. Section 7 classifies c_1 equality graphs and shows that they automatically satisfy this degree condition. Thus H is C_m or I disjoint P_{m-1}. These give precisely C_{n-2} disjoint 2I and P_{n-3} disjoint 3I.

8.2 Excluding graphs with zero or one isolated vertex

Write G = tI disjoint H, where t is zero or one and H has no isolated vertices. Set m = n-t >= 4. For every vertex v of H, equality in (3), followed by the induction hypothesis, says that L_v(G) is a c_2 equality graph on n-1 vertices. It therefore has at least two isolated vertices, maximum degree at most two, and at most one nontrivial component.

By (7), every true-twin class in H has at least 3-t vertices. The degree observation, applied within H, says that every vertex of degree at least three is universal within H.

Suppose H has such a universal vertex u. It has a distinct true twin u’, which is also universal. Any vertex w outside their true-twin class has its own distinct true twin w’. It is adjacent to u,u’,w’, and hence has degree at least three. It must therefore be universal, contrary to being outside the class. Consequently H is complete.

In that case L_v(G) is the edgeless graph on n-1 vertices. Section 4 says an edgeless graph of that order can be extremal only when n-1 = 3 or 4. Since n >= 5, we have n = 5. The only candidates are K_5 and I disjoint K_4. Directly,

$$F_{K_4}=5+6x+4x^2+x^3, \qquad F_{K_5}=5+11x+10x^2+5x^3+x^4.$$

Both candidates have c_2 = 10, strictly below C_5 = 12.

We may therefore assume H has maximum degree at most two. Since it has no isolated vertices and every true-twin class has size at least two, its components can only be K_2 or K_3. When t = 0, the class-size requirement is at least three, so only K_3 components are possible.

Deleting after local complementation at a vertex in a K_s component leaves s-1 isolates from that component and leaves every other component unchanged. Because L_v(G) has at most one nontrivial component, H has at most two components. It cannot have only one: each such component has at most three vertices, while m >= 4. Thus H has exactly two components.

For t = 0, the only candidate is 2K_3. For t = 1, the candidates are I disjoint 2K_2, I disjoint K_2 disjoint K_3, and I disjoint 2K_3. The first has a local-deletion graph 2I disjoint K_2 on four vertices, which is not extremal. The last has a local-deletion graph 3I disjoint K_3 on six vertices, also outside the inductive list.

The remaining two candidates, 2K_3 and I disjoint K_2 disjoint K_3, have the same polynomial:

$$(3+4x+x^2)^2,$$

because (1+x)(3+x) = 3+4x+x^2. Their c_2 coefficient is 22, below C_6 = 24. This eliminates every graph with fewer than two isolates.

8.3 Sufficiency

By (8)-(9), both proposed equality families have polynomial

$$(1+x)^3F_{P_{n-3}}(x).$$

Its coefficient of x^2 is

$$3(U_{n-3}+V_{n-3})=3\cdot2^{n-3}.$$

The equality classification for c_2, and hence all three parts of Problem 8.1 by (1), follows.

9. Evidence, scope, and priority

The proof establishes a stronger algebraic statement for every finite simple graph, including graphs that are not linked-chord graphs. The application to a fixed virtual knot diagram uses the standard circuit-nullity theorem. It makes no claim to solve Problems 8.2 or 8.3, which involve knot invariants minimized over all diagrams.

Executed checks accompanying this note:

• All 33,868 labeled simple graphs on zero through six vertices, using all 2,131,019 diagonal matrices. All upper bounds, both directions of each classification, and F_G(-2) passed.
• All 1,253 unlabeled simple graphs in the NetworkX atlas through seven vertices, with 144,923 diagonal matrices. All classifications passed. Every ordered incident-edge choice was checked against the three-term recursion, giving 24,684 recursion checks; 7,099 checks verified the true-twin observation.
• All 11,465 chord matchings on zero through six chords, covering 697,335 smoothing states. A direct disjoint-set computation of state circles agreed with binary nullity plus one for every state.

The C++ and Python rank implementations use different elimination code. The direct smoothing calculation does not use local-complementation recursion or the classification. These are separate computational checks generated in the same research session, not independent researchers, blind model replications, or formal verification. The proof, rather than the finite census, is what addresses arbitrary crossing number.

A bounded public search located the original state-count paper and the standard circuit-nullity literature but did not establish the priority of this classification. In particular, inability to retrieve the full 2014 journal article and subsequent relevant full texts prevents a comprehensive novelty audit. The 2014 problem list explicitly asks for the classification, but that does not establish that it remained unresolved in September 2026.

References

1. T. Ohtsuki (ed.), Problems on Low-dimensional Topology, 2014, supplied PDF, Problem 8.1 and Figure 6, pp. 11-12. Question contributors: T. Nakamura, Y. Nakanishi, S. Satoh, Y. Tomiyama.
2. T. Nakamura, Y. Nakanishi, S. Satoh, Y. Tomiyama, The state numbers of a virtual knot, Journal of Knot Theory and Its Ramifications 23(3) (2014), 1450016. DOI: 10.1142/S0218216514500163. Bibliographic identity and abstract checked; full journal text not obtained in this session.
3. L. Traldi, Binary nullity, Euler circuits and interlace polynomials, arXiv:0903.4405, Theorem 4, PDF p. 4. https://arxiv.org/abs/0903.4405 . Full relevant definition and theorem checked.