Let $\mathbb{N}$ denote the set of positive integers, and let $G=(V,E)$ be a finite simple, undirected graph. Given $f:V\to \mathbb{Z}$ we define the *neighborhood
sum function* $\mathrm{nsum}\_f:V\to\mathbb{Z}$ by setting 



> 
> $\mathrm{nsum}\_f(v) = \sum\{f(w):w\in N(v)\}$ for all $v\in V$.
> 
> 
> 


We say that a graph $G=(V,E)$ is *sum-balanceable* if there is an injective
function $f:V\to\mathbb{Z}$ such that $\mathrm{nsum}\_f(v) = 0$ for all $v\in V$.


My goal is to prove that sum-balanceability is computable. One way to do this is to show that in order to find an injective $f:V\to\mathbb{Z}$ with the desired property, we only need to check finitely many combinations for assignments of $v\in V$ to an integer. Let's make this hand-waving formal.


**Question.** Is there a computable function $b:\mathbb{N}\to\mathbb{N}$ with the following property?



> 
> Whenever $G=(V,E)$ with $|V| = n\in\mathbb{N}$ is sum-balanceable, there is an injective function $f:V\to \mathbb{Z}$ with $\mathrm{nsum}\_f(v) = 0$ for all $v\in V$ and $$|f(v)| \leq b(n)$$ for all $v\in V$.
> 
> 
> 




---


Note that the existence of such a computable function $b:\mathbb{N}\to\mathbb{N}$ would directly imply that sum-balanceability is computable.



Is sum-balanceability computable?
Yes, there is such a computable function $b$, which follows from the fact that one can compute solutions to [integer programs](https://en.wikipedia.org/wiki/Integer_programming). Note that we can model sum-balanceability by first introducing an integer variable $x\_v$ for each vertex $v \in V(G)$ and writing down the $n$ linear equations $\sum\_{v \in N(u)} x\_v=0$ for each vertex $u \in V(G)$. We still have to ensure that $x\_u \neq x\_v$ for all $u \neq v$, but we can guess the order of the variables and add these as linear inequalities to our integer program. For example, if $V(G)=[n]$, then we can write $x\_n \geq x\_{n-1}+1 \geq x\_{n-2}+2 \geq \dots \geq x\_1+n-1$ to encode the order $x\_n> \dots > x\_1$. Thus, $G$ is sum-balanceable if and only if at least one of the above $n!$ integer programs is feasible. 


In fact, it seems sum-balanceability can be decided in polynomial-time using just linear algebra as follows. Let $A$ be the $V(G) \times V(G)$ adjacency matrix of $G$. Note that $G$ is sum-balanceable if and only if there exists an integer vector $\mathbf x \in \mathbb{Z}^{V(G)}$ in the nullspace of $A$ such that all entries of $\mathbf x$ are distinct. To decide if $\mathbf x$ exists, compute a basis $\mathbf{x}^1, \dots, \mathbf{x}^k$ of the nullspace of $A$. Then $G$ is sum-balanceable if and only if for all distinct $u,v \in V(G)$, there exists $i \in [k]$ such that $\mathbf{x}\_{u}^{i} \neq \mathbf{x}\_{v}^{i}$.


