Sharp existence theorem for Hartke magic graphs

Problem. MathDB #376190, the Low–Roberts conjecture on connected simple Hartke magic graphs.

Primary source. Parikshit Chalise and Richard M. Low, Application of the Combinatorial Nullstellensatz to magic-type graph labelings, arXiv:2607.20724, Definition 2, Conjecture 1, Proposition 1, Proposition 3, and Theorems 4 and 7. The conjecture was originally posed by Richard M. Low and Dan Roberts, Constructing integer-magic graphs via the Combinatorial Nullstellensatz, Art of Discrete and Applied Mathematics 5 (2022), P2.04, doi:10.26493/2590-9770.1401.a6a.

The 2026 paper proves the conjecture when $p=3$, and, for every prime $p\geq5$, proves existence only in the range $n\geq p$. We resolve the remaining range $6\leq n<p$ and determine the exact existence threshold for every odd prime:

$$\boxed{ \begin{array}{ll} p=3: &\text{a connected simple Hartke }\mathbb F_3 \text{-magic graph of order }n \text{ exists if and only if }n\geq6;\\ p\geq5: &\text{a connected simple Hartke }\mathbb F_p \text{-magic graph of order }n \text{ exists if and only if }n\geq4. \end{array} } \tag{1}$$

In particular, the conjectured existence for every prime $p\geq3$ and every $n\geq6$ follows.

1. The precise Hartke-term condition

For a finite simple graph $G=(V,E)$ and $t\in\mathbb F_p$, the source defines

$$f_{G,t}(x) =\prod_{v\in V} \left[ 1-\left(t-\sum_{e\ni v}x_e\right)^{p-1} \right]. \tag{2}$$

The graph is Hartke $\mathbb F_p$-magic if this polynomial contains a monomial of total degree $(p-1)|V|$ with nonzero coefficient and with every individual edge exponent at most $p-2$. Its highest homogeneous component is

$$(-1)^{|V|}\mathcal H_G(x), \qquad \mathcal H_G(x) =\prod_{v\in V} \left(\sum_{e\ni v}x_e\right)^{p-1}. \tag{3}$$

Here $p-1$ is even, so replacing $t-\sum x_e$ by $-\sum x_e$ introduces no additional sign. Consequently, it suffices to find a nonzero coefficient in $\mathcal H_G$ whose exponents are all at most $p-2$.

2. A prime-uniform four-vertex seed

Let $p\geq5$ be prime, and label the six edges of $K_4$ by

$$a=x_{01},\qquad b=x_{02},\qquad c=x_{03},\qquad d=x_{12},\qquad e=x_{13},\qquad f=x_{23}. \tag{4}$$

Then

$$\mathcal H_{K_4} =(a+b+c)^{p-1}(a+d+e)^{p-1} (b+d+f)^{p-1}(c+e+f)^{p-1}. \tag{5}$$

We claim the exact finite-field coefficient identity

$$\boxed{ \left[a\,b^3c^{p-2}d^{p-2}e^{p-2}f^{p-2}\right] \mathcal H_{K_4}=1 \quad\text{in }\mathbb F_p. } \tag{6}$$

Every displayed exponent lies between $1$ and $p-2$, including the endpoint $p=5$, where $3=p-2$. Moreover, their sum is

$$1+3+4(p-2)=4(p-1). \tag{7}$$

Thus (6) proves that $K_4$ is Hartke $\mathbb F_p$-magic for every prime $p\geq5$.

To establish (6), recall the elementary finite-field power-sum identity

$$\sum_{z\in\mathbb F_p}z^j = \begin{cases} -1,&j>0\text{ and }p-1\mid j,\\ 0,&\text{otherwise}. \end{cases} \tag{8}$$

In particular, the case $j=0$ gives $p=0$ in $\mathbb F_p$.

Set

$$\Omega(a,b,c,d,e,f)=a^{p-2}b^{p-4}cdef. \tag{9}$$

This monomial has degree $2(p-1)$. Therefore, every monomial in $\Omega\mathcal H_{K_4}$ has total degree $6(p-1)$. Summing such a monomial over $\mathbb F_p^6$ gives zero unless the exponent of each of its six variables is a positive multiple of $p-1$. Because their total degree is exactly $6(p-1)$, all six exponents must then equal $p-1$. Hence the only surviving monomial of $\mathcal H_{K_4}$ is precisely the one in (6), and the six factors $-1$ from (8) have product $1$. It follows that

$$\left[a\,b^3c^{p-2}d^{p-2}e^{p-2}f^{p-2}\right] \mathcal H_{K_4} = \sum_{(a,b,c,d,e,f)\in\mathbb F_p^6} \Omega(a,b,c,d,e,f)\mathcal H_{K_4}(a,b,c,d,e,f). \tag{10}$$

Write

$$L_0=a+b+c,\qquad L_1=a+d+e,\qquad L_2=b+d+f,\qquad L_3=c+e+f. \tag{11}$$

For each field element $z$, Fermat's theorem gives

$$z^{p-1}=1-\mathbf 1_{\{z=0\}}. \tag{12}$$

Consequently, the right-hand side of (10) is

$$\sum_{J\subseteq\{0,1,2,3\}} (-1)^{|J|} \sum_{x\in\bigcap_{j\in J}\ker L_j}\Omega(x). \tag{13}$$

Every proper subset of the four incidence forms is linearly independent: if $i\in J$ and $j\notin J$, then the edge variable $x_{ij}$ occurs in $L_i$ but in none of the other forms indexed by $J$. The full set is also independent. Indeed,

$$\sum_{i=0}^{3}\lambda_iL_i=0 \quad\Longrightarrow\quad \lambda_i+\lambda_j=0 \quad(0\leq i<j\leq3), \tag{14}$$

and any triangle then gives $2\lambda_i=0$. Since $p$ is odd, all $\lambda_i$ vanish. Therefore

$$\dim\left(\bigcap_{j\in J}\ker L_j\right)=6-|J|. \tag{15}$$

When $J$ is proper, this dimension is at least $3$. Choose linear coordinates $z_1,\ldots,z_d$ on the corresponding kernel, where $d\geq3$. The restriction of $\Omega$ is a homogeneous polynomial of degree $2(p-1)$. In every monomial of that restriction, at least one coordinate has exponent strictly less than $p-1$. Summing first over that coordinate and applying (8) gives

$$\sum_{x\in\bigcap_{j\in J}\ker L_j}\Omega(x)=0 \qquad \bigl(J\subsetneq\{0,1,2,3\}\bigr). \tag{16}$$

Only the term with all four constraints remains in (13). Its kernel is parametrized by

$$(a,b,c,d,e,f) =(u,v,-u-v,-u-v,v,u), \qquad u,v\in\mathbb F_p. \tag{17}$$

On this kernel,

$$\begin{aligned} \Omega &=u^{p-1}v^{p-3}(u+v)^2\\ &=u^{p+1}v^{p-3} +2u^pv^{p-2} +u^{p-1}v^{p-1}. \end{aligned} \tag{18}$$

The first two terms have $v$-exponents strictly between $0$ and $p-1$, so their sums vanish by (8). The last term contributes

$$\left(\sum_{u\in\mathbb F_p}u^{p-1}\right) \left(\sum_{v\in\mathbb F_p}v^{p-1}\right) =(-1)^2=1. \tag{19}$$

Equations (10)–(19) prove (6).

3. Adding a vertex with just two neighbors

The source's Proposition 3 requires the new vertex to have exactly $p-1$ neighbors. In fact, only two neighbors are necessary.

Two-neighbor extension lemma. Let $p\geq3$ be prime, let $G$ be a Hartke $\mathbb F_p$-magic graph, and let $G^+$ be obtained by adjoining a new vertex adjacent to at least two distinct vertices of $G$. Then $G^+$ is also Hartke $\mathbb F_p$-magic.

Proof. Let $M$ be a Hartke monomial for $G$, so

$$\deg M=(p-1)|V(G)|, \qquad [M]\mathcal H_G\neq0, \qquad \deg_{x_e}M\leq p-2. \tag{20}$$

Write $y_1,\ldots,y_s$ for the edges incident to the new vertex, where $s\geq2$. In the product of the factors belonging to the old vertices, the total degree is $(p-1)|V(G)|$. Since $M$ already has precisely this total degree in the old edge variables, a contribution to its coefficient cannot contain any of the new variables. Consequently,

$$\begin{aligned} \left[M y_1y_2^{p-2}\right]\mathcal H_{G^+} &= [M]\mathcal H_G\, \left[y_1y_2^{p-2}\right] (y_1+\cdots+y_s)^{p-1}\\ &= \binom{p-1}{1}[M]\mathcal H_G\\ &=-[M]\mathcal H_G\neq0 \qquad\text{in }\mathbb F_p. \end{aligned} \tag{21}$$

Both new positive exponents, $1$ and $p-2$, satisfy the Hartke bound, and all other new variables have exponent zero. Thus the displayed monomial is a Hartke term for $G^+$. $\square$

By (6), the complete graph $K_4$ is a valid seed for every prime $p\geq5$. Repeatedly adjoin a vertex adjacent to any two existing vertices. This produces a connected simple Hartke $\mathbb F_p$-magic graph of every order

$$n\geq4. \tag{22}$$

One explicit choice is to connect every newly adjoined vertex to the same two original vertices of $K_4$. This graph has $2n-2$ edges.

For $p=3$, Theorem 4 of the primary source already proves existence for every $n\geq6$. For completeness, the next section supplies an explicit seed and verifies that this threshold is sharp.

4. An explicit six-vertex seed in characteristic three

Let $G_6$ be the join of a four-vertex path and a two-vertex complete graph:

$$G_6=P_4\vee K_2. \tag{23}$$

Concretely, take the path $0-3-2-1$, take the additional edge $45$, and join both $4$ and $5$ to each path vertex. Thus

$$E(G_6)= \{03,04,05,12,14,15,23,24,25,34,35,45\}. \tag{24}$$

When $p=3$, the only possible exponent of an edge in a full-degree monomial is at most one. Since $G_6$ has six vertices and twelve edges, its candidate Hartke monomial is

$$M_6=\prod_{e\in E(G_6)}x_e. \tag{25}$$

Every contribution to $[M_6]\mathcal H_{G_6}$ chooses exactly two distinct incident edges from each factor

$$\left(\sum_{e\ni v}x_e\right)^2. \tag{26}$$

Each such choice has coefficient $2$. Assigning each edge to the endpoint whose factor supplied its variable is equivalent to orienting every edge so that all six vertices have indegree $2$. Therefore

$$[M_6]\mathcal H_{G_6}=2^6N_2(G_6), \tag{27}$$

where $N_2(G_6)$ denotes the number of such orientations.

To count these orientations, first direct the edge $45$ from $4$ to $5$; the opposite choice gives the same count by symmetry. Orient the three path edges in the listed order $03,32,21$, writing $1$ when the edge points forward along the path. The number of admissible orientations of the eight remaining edges is

$$\begin{array}{c|cccccccc} \text{path orientation}&000&001&010&011&100&101&110&111\\ \hline \text{admissible completions}&3&3&1&3&1&1&1&3. \end{array} \tag{28}$$

For an elementary explanation of each entry, let $r_i$ be the number of edges from the universal vertices $4,5$ that must point into path vertex $i$. If its indegree within the path is $d_i$, then

$$r_i=2-d_i, \qquad \sum_{i\in V(P_4)}r_i=5. \tag{29}$$

A column with $r_i=2$ leaves no edge pointing into $4$ or $5$, a column with $r_i=0$ contributes one edge into each, and a column with $r_i=1$ contributes an edge into exactly one of them. Because $45$ points from $4$ to $5$, the cross edges must supply two incoming edges at $4$ and one at $5$.

If none of the $r_i$ is zero, their multiset is $(2,1,1,1)$, and there are $\binom32=3$ choices. Otherwise their multiset is $(2,2,1,0)$, and the completion is forced. Applying this rule to the eight path orientations gives exactly (28). Hence

$$N_2(G_6) =2(3+3+1+3+1+1+1+3) =32. \tag{30}$$

In particular,

$$[M_6]\mathcal H_{G_6} =2^6\cdot32 \equiv2\pmod3, \tag{31}$$

so $G_6$ is Hartke $\mathbb F_3$-magic. This recovers the seed and the coefficient from Example 2 of the source. Repeated application of the two-neighbor extension lemma gives connected simple examples of every order $n\geq6$, with exactly

$$12+2(n-6)=2n \tag{32}$$

edges.

5. The thresholds are best possible

The source's Proposition 1 gives the universal necessary edge bound

$$|E(G)|\geq\frac{p-1}{p-2}|V(G)|. \tag{33}$$

For a simple graph of order $n\leq3$,

$$|E(G)|\leq\binom n2\leq n <\frac{p-1}{p-2}n, \tag{34}$$

so no such graph is Hartke $\mathbb F_p$-magic for any odd prime $p$. This proves that the threshold $n=4$ in characteristic $p\geq5$ is sharp.

When $p=3$, condition (33) becomes

$$|E(G)|\geq2n. \tag{35}$$

This is impossible for a simple graph with $n\leq4$. When $n=5$, the bound forces

$$|E(G)|=10, \qquad G=K_5. \tag{36}$$

Since the required degree is $2n=10$ and every allowed exponent is at most $1$, the only candidate Hartke term is the product of all ten edge variables. As in (27), its coefficient is

$$2^5N_2(K_5), \tag{37}$$

where $N_2(K_5)$ is the number of regular tournaments on five labeled vertices.

There are exactly

$$N_2(K_5)=\binom42\cdot2\cdot2=24. \tag{38}$$

Indeed, choose the two vertices defeated by vertex $0$ in $\binom42$ ways. Orient the edge joining those two vertices in $2$ ways. Its winner must defeat exactly one of the two vertices that defeat $0$, giving another $2$ choices. The remaining edges are then forced by the required outdegree $2$. Consequently,

$$2^5N_2(K_5)=2^5\cdot24\equiv0\pmod3. \tag{39}$$

Thus $K_5$ is not Hartke $\mathbb F_3$-magic, and neither is any graph of smaller order. Together with (22) and (31)–(32), this proves the sharp classification (1). The characteristic-three constructions also attain the necessary lower bound (35), so they have the minimum possible number of edges.

Status. The Low–Roberts conjecture is PROVED for every prime and every conjectured order; the stronger exact order thresholds are also determined.