A complete proof of the bipartite supertoken independence-number conjecture

Problem. MathDB #374083, “The supertoken graph independence-number conjecture for bipartite graphs.”

Primary source. Mónica A. Reyes, Cristina Dalfó, and Miquel Àngel Fiol, On supertoken graphs, arXiv:2604.06164v1, April 7, 2026, Theorem 3.4 and Conjecture 3.6. The source's conjecture refers to its displayed bound as an “upper bound,” but Theorem 3.4 actually states the independent-set lower bound. The mathematical claim is equality in that displayed bound.

Theorem

Let $G$ be a finite simple bipartite graph with a specified bipartition

$$V(G)=C_1\sqcup C_2, \qquad |C_1|=c_1\leq c_2=|C_2|,$$

and suppose that

$$\alpha(G)=c_2.$$

For every integer $k\geq 0$, the $k$-supertoken graph satisfies

$$\boxed{\displaystyle \alpha\!\left(\mathcal F_k(G)\right) =\sum_{j=0}^{\lfloor k/2\rfloor} \binom{c_1+2j-1}{2j} \binom{c_2+k-2j-1}{k-2j}.} \tag{1}$$

When a color class is empty, a binomial coefficient in (1) means the number of weak compositions into that class: this number is $1$ when the prescribed total is zero and $0$ otherwise. Thus (1) also includes the empty-class and empty-graph cases. The source asks only for $k\geq 2$.

More strongly, the supertoken graph has an explicit matching that saturates every vertex containing an odd number of tokens on $C_1$. Consequently, the answer depends only on $c_1,c_2,k$, not on any further edges of $G$.

1. Translating the hypothesis into a saturating matching

For a finite graph, let $\nu(G)$ denote its maximum matching size. The vertex-cover identity and König's theorem give, for every finite bipartite graph,

$$\alpha(G)=|V(G)|-\nu(G). \tag{2}$$

Consequently, the hypothesis $\alpha(G)=c_2$ is equivalent to

$$\nu(G)=c_1. \tag{3}$$

Thus there is a matching saturating the entire smaller color class. Label it

$$M=\{a_1b_1,\ldots,a_{c_1}b_{c_1}\}, \qquad a_i\in C_1, \quad b_i\in C_2, \tag{4}$$

and write $d=c_2-c_1$ for the number of remaining vertices of $C_2$.

Let $H$ be the spanning subgraph of $G$ whose only edges are those of $M$; the other $d$ vertices are isolated. Every token move allowed in $H$ is also allowed in $G$, so

$$\mathcal F_k(H)\subseteq\mathcal F_k(G) \tag{5}$$

as a spanning subgraph.

2. Decomposition into rectangular grids

A vertex of $\mathcal F_k(G)$ is a weak composition

$$x=(x_v)_{v\in V(G)}, \qquad x_v\in\mathbb Z_{\geq0}, \qquad \sum_{v\in V(G)}x_v=k. \tag{6}$$

Two compositions are adjacent exactly when one is obtained from the other by moving one token along an edge of $G$. Tokens are indistinguishable, arbitrary multiplicities are allowed, and no loops or additional adjacency rules are introduced.

For the matching subgraph $H$, define the invariants

$$t_i=x_{a_i}+x_{b_i} \quad(1\leq i\leq c_1),$$

together with the token counts on the $d$ isolated vertices. Moving a token along $a_ib_i$ changes $x_{a_i}$ by $1$ and $x_{b_i}$ by $-1$, or conversely, and preserves all these invariants.

Conversely, after fixing every $t_i$ and every isolated-vertex count, the independent coordinates

$$z_i=x_{a_i}\in\{0,1,\ldots,t_i\} \tag{7}$$

describe the entire corresponding connected component. Its graph is exactly the Cartesian rectangular grid

$$P_{t_1+1}\mathbin{\square}\cdots\mathbin{\square}P_{t_{c_1}+1}. \tag{8}$$

Here $P_r$ is the path with $r$ vertices; factors with $t_i=0$ are singleton paths. A grid vertex has parity

$$\varepsilon(z)=z_1+\cdots+z_{c_1}\pmod 2. \tag{9}$$

This is precisely the parity of the total number of tokens on $C_1$.

3. An explicit matching saturating every odd grid vertex

Fix one component (8).

First suppose that at least one $t_i$ is odd. Choose any such index $i$. Since $t_i+1$ is even, pair the vertices of the $i$th coordinate path as

$$0\longleftrightarrow1, \quad 2\longleftrightarrow3, \quad\ldots\quad, t_i-1\longleftrightarrow t_i. \tag{10}$$

Keep all other coordinates fixed. These edges form a perfect matching of the whole grid. In particular, every odd-parity vertex is matched.

Now suppose that every $t_i$ is even. In the first coordinate, use the pairs

$$0\longleftrightarrow1, \quad 2\longleftrightarrow3, \quad\ldots\quad, t_1-2\longleftrightarrow t_1-1, \tag{11}$$

for every choice of the remaining coordinates. The only vertices not yet matched lie in the hyperplane $z_1=t_1$. Within that hyperplane, perform the analogous consecutive pairing in coordinate $z_2$, leaving only the subhyperplane

$$z_1=t_1, \qquad z_2=t_2.$$

Continue through all coordinates. Earlier hyperplanes never overlap an already chosen matching edge, so the result is a matching of every grid vertex except

$$(t_1,t_2,\ldots,t_{c_1}). \tag{12}$$

Since every $t_i$ is even, this remaining vertex has even parity. Thus every odd-parity grid vertex is matched in this case as well. The construction also handles zero coordinates: when $t_i=0$, that step has no pairs and simply retains the same hyperplane.

Taking the union of these componentwise matchings produces a matching of $\mathcal F_k(H)$, hence by (5) also of $\mathcal F_k(G)$, that saturates its entire odd-parity class.

4. Exact independence and evaluation of the even class

Write

$$S_{\mathrm{even}} =\left\{x:\sum_{a\in C_1}x_a\equiv0\pmod2\right\}, \qquad S_{\mathrm{odd}} =\left\{x:\sum_{a\in C_1}x_a\equiv1\pmod2\right\}. \tag{13}$$

Every allowed token move exchanges the two parity classes, so they form a bipartition of $\mathcal F_k(G)$. The matching constructed above saturates $S_{\mathrm{odd}}$. Consequently,

$$|S_{\mathrm{odd}}| \leq\nu\!\left(\mathcal F_k(G)\right) \leq |S_{\mathrm{odd}}|,$$

where the second inequality holds because every matching edge uses one odd-parity vertex. Therefore

$$\nu\!\left(\mathcal F_k(G)\right)=|S_{\mathrm{odd}}|. \tag{14}$$

Applying König's theorem to the bipartite supertoken graph gives

$$\alpha\!\left(\mathcal F_k(G)\right) =|S_{\mathrm{even}}|+|S_{\mathrm{odd}}|-|S_{\mathrm{odd}}| =|S_{\mathrm{even}}|. \tag{15}$$

In particular, $S_{\mathrm{even}}$ itself is a maximum independent set, and $S_{\mathrm{odd}}$ is a minimum vertex cover.

If exactly $2j$ tokens lie on $C_1$, stars and bars gives

$$\binom{c_1+2j-1}{2j}$$

possible weak compositions on $C_1$ and

$$\binom{c_2+k-2j-1}{k-2j}$$

possible weak compositions on $C_2$. Summing over $0\leq j\leq\lfloor k/2\rfloor$ proves (1), and therefore proves Conjecture 3.6 in full.

5. Exact generating functions and boundary cases

The parity filter gives the additional rational generating function

$$\boxed{\displaystyle \sum_{k\geq0}\alpha\!\left(\mathcal F_k(G)\right)z^k =\frac12\left( \frac1{(1-z)^{c_1+c_2}} +\frac1{(1+z)^{c_1}(1-z)^{c_2}} \right).} \tag{16}$$

Furthermore, the number of unmatched even vertices in the explicit maximum matching has generating function

$$\sum_{k\geq0} \left(|S_{\mathrm{even}}|-|S_{\mathrm{odd}}|\right)z^k =\frac1{(1-z^2)^{c_1}(1-z)^{c_2-c_1}}, \tag{17}$$

whose coefficients are manifestly nonnegative. This also independently explains why the even parity class is never smaller than the odd class.

For $k=0$, there is one empty token placement, and (1) gives $1$. For $k=1$, $\mathcal F_1(G)=G$, and (1) gives $c_2$, recovering the hypothesis. If $c_1=0$, then $G$ has no edges and every placement is even; thus

$$\alpha\!\left(\mathcal F_k(G)\right) =\binom{c_2+k-1}{k}$$

when $c_2>0$, exactly as prescribed by the empty-class convention in (1). If both classes are empty, the unique placement occurs at $k=0$ and no placements exist for $k>0$. No connectedness assumption is needed anywhere.

Earlier results of de Alba, Carballosa, Leaños, and Rivera concern ordinary token graphs, where each vertex can hold at most one token; they do not establish this arbitrary-multiplicity supertoken result. The grid decomposition and matching above resolve the distinct 2026 supertoken conjecture directly.