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

  • 2
    $\begingroup$ The statement "for $n\geq 4$ the circle $C_n$ does not have a non-trivial parity map" is false. E.g., for $n=6$, a non-trivial parity map does exist, 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:01
  • 1
    $\begingroup$ If $n$ is even, then the complete bipartite graph $K_{n,n}$ has minimal degree $n$ and does not admit a non-trivial parity map. $\endgroup$ – Philipp Lampe Mar 2 '18 at 10:24
  • $\begingroup$ For completeness, let me note that, curiously, $n=4$ is the only natural 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 connected multigraph', 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\}$ are unique and 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
  • $\begingroup$ Dear @Dominic van der Zypen: for completeness, and to prevent the (admittedly unlikely) eventuality that a future reader who needs exactly this concept (and does not read up to the comments-section) is misled, I struck out a false statement, leaving it visible, so as to keep a comment meaningful. I hope you agree with this (if MO aspires to be some sort of living reference work, then even small errors should be corrected), but of course, needless to say, you can also delete the statement entirely if you prefer. $\endgroup$ – Peter Heinig Mar 2 '18 at 15:59
  • $\begingroup$ Thanks @PeterHeinig, sorry for being a bit sloppy! I'll leave the statement as is, as it was my mistake, and if it deleted, the comments pointing to a deleted line of mine might confuse other readers. It was a good idea of yours just to strike the false statement but not delete it $\endgroup$ – Dominic van der Zypen Mar 3 '18 at 7:49

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.