(This question actually arose in real life when dealing with status bits with mutual influence.)

Let $G=(V,E)$ be a connected, simple, undirected graph with $|V| \geq 2$. For $v\in V$, let $N_G(v) = \{w\in V: \{v,w\}\in E\}$. A *parity map* for $G$ is a map $f:V\to {\mathbb Z}/2{\mathbb Z}$ such that for every $v\in V$ we have $$f(v) = \sum_{w\in N_G(v)}f(w).$$ We say a parity function is *non-trivial* if it is not $0$ everywhere. For example, the complete graphs $K_n$ all have non-trivial parity maps: if $n$ is even, the constant $1$ map is a parity map, and for $n$ odd, pick one vertex, map it to $0$, and map the other points to $1$. ~~Note that for $n\geq 4$ the circle $C_n$ does not have a non-trivial parity map. ~~

**Question.** Is there for every $n\in \mathbb{N}$ a connected graph $G$ with minimal degree $\delta(G) = n$ such that $G$ has no non-trivial parity maps?

false. E.g., for $n=6$, a non-trivial parity mapdoesexist, e.g. (the matrix is meant to represent a circuit, e.g. by reading it clockwise): $\begin{matrix} 1 \quad- & 0\quad- & 1\quad \\ \hspace{-18pt}| & & \hspace{-10pt}|\\ 1\quad- & 0\quad - & 1\quad\end{matrix}$. $\endgroup$ – Peter Heinig Mar 2 '18 at 10:01onlynatural number such that the $n$-circuit $C_n$ does not admit a non-trivial parity map. One can even push this to $n\in\{0,1,2\}$ if one agrees that '$n$-circle'='$n$-vertex 2-regular connectedmultigraph', then this everything works. (For $n=1$, it's the loop.) The non-trivial parity maps in the cases $n\in\{3\}\cup\{k: k\geq 5\}$ areuniqueand easy to find. In a sense, you have discovered a characterization of the number $4$: a number $n$ is equal to $4$ iff the 'circle' on $n$ vertices admits a nontrivial parity map. $\endgroup$ – Peter Heinig Mar 2 '18 at 15:44