(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?



Non-trivial parity maps in graphs
I think $K\_{n,n+1}$ works. Clearly each side must be monochromatic. So the side of odd size must be all $0$. But then the other side must be all $0$.


