Closed-form conjecture for the precoloring polynomial of the hexwheel network

The hexwheel precoloring formula, its two-variable extension, and the corrected recurrence

Let $D_m$ be the network in Example 6.4 of Bob Lutz, Matroids arising from electrical networks, Advances in Applied Mathematics 137 (2022), 102331, arXiv:1809.10100v5. Its $m\geq3$ interior vertices form a cycle, and each is adjacent to its own distinct pendant boundary vertex. Write $\chi_m(q)$ for its precoloring polynomial.

We prove the radical closed form in Conjecture 6.5 for every $m$, establish a stronger two-variable identity, and correct the recurrence printed in the same conjecture, which is incompatible with both the closed form and its displayed initial polynomials.

A general precoloring identity

More generally, let $D=(G,B)$ be any finite loopless network with boundary $B$, interior vertex set $I$, and interior graph $H=G[I]$. Give the boundary vertices distinct prescribed colors from a palette of $q\geq |B|$ colors. For $C\subseteq I$, put

$$b(C)=\bigl|\{u\in B:u\text{ is adjacent to some }v\in C\}\bigr|. \tag{1}$$

For $A\subseteq E(H)$, let $\pi(A)$ denote the connected components of the spanning graph $(I,A)$, including isolated vertices. Inclusion-exclusion over the events that the endpoints of an interior edge receive the same color gives

$$\boxed{ \chi_D(q)= \sum_{A\subseteq E(H)}(-1)^{|A|} \prod_{C\in\pi(A)}\bigl(q-b(C)\bigr). } \tag{2}$$

Indeed, if all equalities corresponding to $A$ hold, every component $C$ receives a common color. Exactly $b(C)$ colors are forbidden by its adjacent boundary vertices, so its color can be chosen in $q-b(C)$ ways independently of the other components. The equality holds for every integer $q\geq |B|$, hence is an identity of polynomials.

For $D_m$, every interior vertex has its own distinct boundary neighbor, and therefore

$$b(C)=|C|. \tag{3}$$

Introduce the stronger two-variable spanning-subgraph polynomial

$$Z_m(q,t)= \sum_{A\subseteq E(C_m)}t^{|A|} \prod_{C\in\pi(A)}(q-|C|), \qquad \chi_m(q)=Z_m(q,-1). \tag{4}$$

For integer $q\geq m$, $Z_m(q,t)$ also counts all colorings avoiding their distinct prescribed forbidden colors, with each monochromatic cycle edge contributing a factor $1+t$.

Evaluation by cyclic interval compositions

For a component consisting of $j\geq1$ consecutive cycle vertices and $j-1$ selected edges, define

$$w_j=t^{j-1}(q-j), \qquad W(z)=\sum_{j\geq1}w_jz^j =\frac{z(q-1-qtz)}{(1-tz)^2}. \tag{5}$$

Consider a proper subset $A\subsetneq E(C_m)$, and let $k\geq1$ be the number of omitted cycle edges. Its components are cyclic intervals with lengths $j_1,\ldots,j_k$, and its contribution is $\prod_i w_{j_i}$. Marking one omitted edge counts each such edge subset $k$ times. Alternatively, choose its marked starting location in $m$ ways and then choose an ordered composition of $m$ into $k$ positive parts. Consequently,

$$\sum_{\substack{A\subsetneq E(C_m)\\|E(C_m)\setminus A|=k}} t^{|A|}\prod_{C\in\pi(A)}(q-|C|) =\frac{m}{k}[z^m]W(z)^k. \tag{6}$$

The one omitted case $A=E(C_m)$ contributes $t^m(q-m)$. Summing (6) over $k\geq1$ therefore yields

$$Z_m(q,t) =[z^m]\frac{zW'(z)}{1-W(z)}+t^m(q-m). \tag{7}$$

Set

$$\begin{aligned} R(z)&=1-(q-1+2t)z+t(q+t)z^2,\\ \rho_\pm&= \frac{q-1+2t\pm\sqrt{(q-1)^2-4t}}{2}. \end{aligned} \tag{8}$$

Then $1-W(z)=R(z)/(1-tz)^2$ and $R(z)=(1-\rho_+z)(1-\rho_-z)$. Formal logarithmic differentiation gives

$$\frac{zW'(z)}{1-W(z)} =-\frac{zR'(z)}{R(z)}-\frac{2tz}{1-tz} =\sum_{j\geq1}\bigl(\rho_+^j+\rho_-^j-2t^j\bigr)z^j. \tag{9}$$

Combining (7) and (9) proves the complete bivariate formula

$$\boxed{ Z_m(q,t)=\rho_+^m+\rho_-^m+t^m(q-m-2) \qquad(m\geq3). } \tag{10}$$

Although radicals conveniently express the two roots, their power sum belongs to $\mathbb Z[q,t]$. Indeed it is determined by the recurrence with characteristic polynomial $X^2-(q-1+2t)X+t(q+t)$.

The identical component argument also evaluates the associated path network. If $P_m$ replaces $C_m$ while each interior vertex retains its distinct pendant boundary neighbor, then

$$\sum_{m\geq0}Z_{P_m}(q,t)z^m =\frac1{1-W(z)} =\frac{(1-tz)^2}{1-(q-1+2t)z+t(q+t)z^2}. \tag{11}$$

The conjectured closed form and the necessary correction

Putting $t=-1$ in (8)--(10) gives

$$\boxed{ \chi_m(q)= \left(\frac{q-3+\sqrt{(q-1)^2+4}}2\right)^m +\left(\frac{q-3-\sqrt{(q-1)^2+4}}2\right)^m +(-1)^m(q-m-2). } \tag{12}$$

With $q=\lambda+1$ and $\omega_\pm=\lambda-2\pm\sqrt{\lambda^2+4}$, this becomes exactly the closed form asserted in the published Conjecture 6.5:

$$\boxed{ \chi_m(\lambda+1) =\frac{\omega_+^m+\omega_-^m}{2^m} +(-1)^m(\lambda-m-1). } \tag{13}$$

The two radical terms in (12) satisfy the homogeneous recurrence with coefficients $q-3$ and $q-1$. Substituting the remaining term $(-1)^m(q-m-2)$ gives the correct inhomogeneous recurrence

$$\boxed{ \chi_{m+2}(q) =(q-3)\chi_{m+1}(q)+(q-1)\chi_m(q) +(-1)^m(m-2q+3). } \tag{14}$$

In particular,

$$\begin{aligned} \chi_3(q)&=q^3-6q^2+14q-13,\\ \chi_4(q)&=q^4-8q^3+28q^2-51q+41,\\ \chi_5(q)&=q^5-10q^4+45q^3-115q^2+169q-116. \end{aligned} \tag{15}$$

The published initial values $\chi_3$ and $\chi_4$ agree with (15), but its subsequent displayed recurrence instead asserts

$$\chi_{m+2}(q) =(q-1)\chi_{m+1}(q)+(q+1)\chi_m(q) +(-1)^m(m-2q-1). \tag{16}$$

At $m=3$, its right-hand side minus the actual $\chi_5(q)$ equals

$$2\bigl(q^4-7q^3+22q^2-37q+30\bigr)\neq0. \tag{17}$$

For instance, the actual number of extensions at $q=5$ is $\chi_5(5)=354$, whereas (16) predicts $644$. The printed recurrence has been shifted by two units: its displayed coefficients and inhomogeneous term are correct for the translated sequence $\chi_m(q+2)$, not for $\chi_m(q)$.

Thus the substantive closed-form assertion of Conjecture 6.5 is true for every $m\geq3$, the source's additional recurrence assertion is false as printed, and (14) gives the corrected recurrence. Equations (2), (10), and (11) additionally establish the arbitrary-network precoloring identity, the full two-variable cycle refinement, and its companion path formula.