We explain the way to write integers between \(1\) and \(2^N-1\) to satisfy the condition.

Rephrasing the condition

Let us first describe the condition of the problem statement using matrices and vectors. In the following discussion, addition and multiplication are modulo \(2\); XOR is merely addition modulo \(2\).

Let \(A\) be the adjacency matrix of the given graph; in other words, \(A\) is the \((N \times N)\) matrix such that \(A_{ij}=1\) if there is an edge between vertices \(i\) and \(j\), and \(A_{ij}=0\) otherwise.

Also, let \(x_{k,i}\) denote the \(k\)-th bit of the integer to be written on vertex \(i\) (\(0 \leq k \leq N-1\)), and \(x_k = (x_{k,1},\dots,x_{k,N})\) be the vector collected for all \(i\).

The condition that the XOR of the integers written on the vertices adjacent to every vertex is represented as follows:

\(\sum_{j=1}^N A_{ij} x_{k,j} = 0\) for all \(i=1,2,\dots,N\) and \(k=0,1,\dots,N-1\),

Using matrix multiplication, we can write as follows:

\(Ax_k = 0\) for all \(k=0,1,\dots,N-1\).

The condition that any integer written on a vertex is non-zero is equivalent to:

for all \(i\,(1\leq i \leq N)\), at least one of \(x_{0,i},\dots,x_{N-1,i}\) is \(1\). In other words, every element of the bitwise OR of \(x_0,\dots,x_{N-1}\) is \(1\).

Therefore, it is sufficient to choose \(N\), \(N\)-dimensional vectors \(x\) consisting of \(0\) and \(1\) such that \(Ax=0\), so that for every component there exists at least one vector with that element being \(1\).

How to find conforming \(x_0,x_1,\dots,x_{N-1}\)?

The vectors \(x\) with \(Ax = 0\) are closed under XOR. That is, if \(x\) and \(x'\) satisfy \(Ax=0\) and \(Ax'=0\), then the vector \(x''=x + x'\) also satisfies \(Ax''= 0\).

The set \(S\) consisting of \(N\)-dimensional binary vectors closed under XOR has a basis. A basis of \(S\) is a set of vectors \(B=\{b_1,b_2,\dots,b_m\}\) such that:

• any element of \(S\) can be represented as the XOR of some vectors chosen from \(B\); and
• the XOR of one or more elements of \(B\) is never \(0\).

There are at most \(N\) elements in a basis.

Let \(b_1,b_2,\dots,b_m\) be a basis of the set \(S\) of the vectors satisfying \(Ax=0\). If every element of their bitwise OR is \(1\), then one can obtain conforming \(x_0,x_1,\dots,x_{N-1}\) by setting \(x_0=b_1,x_1=b_2,\dots,x_{m-1}=b_m,x_m=x_{m+1}=\dots=x_{N-1}=0\) for example. Conversely, if there is a \(0\) element in the bitwise OR of the basis, then for every vector in \(S\), which is represented as the XOR of elements of \(B\), its corresponding component is \(0\). Thus, it is impossible to satisfy the condition in this case.

Therefore, the problem can be solved by finding a basis of the solution set of the system of equations \(Ax=0\). Generally, the solution of a system of equations \(Ax=b\) can be found using the algorithm called Gaussian elimination. This algorithm is explained in the following articles:

• Article by drken (Japanese): https://drken1215.hatenablog.com/entry/2019/03/20/202800
• Article in cp-algorithms (English): https://cp-algorithms.com/linear_algebra/linear-system-gauss.html

One can represent \(N\)-dimensional binary vectors \((N \leq 60)\) as a 64-bit integer, which enables \(O(N^2)\) Gaussian elimination.