**Added (24.08.2019):** As I consider this question important for quantum physics, I have announced a 3000 Euro award on its solution, see here for more details.

**Added (19.09.2019):** This problem can be rephrased entirely in terms of equation systems, without the connections to graph theory, as Alex Ravsky has already suggested.

The following purely graph-theoretic question is motivated by quantum mechanics (and a special case of the questions asked here).

**Bi-Colored Graph**: A bi-colored weighted graph $G=(V(G),E(G))$, on $n$ vertices with $d$ colors is an undirected, not necessarily simple graph where there is a fixed ordering of the vertices $V(G)=v_1, \ldots, v_n$ and to each edge $e \in E(G)$ there is a complex weight $w_e$ and an ordered pair of (not necessarily different) colors $(c_1(e),c_2(e))$ associated with it from the $d$ possible colors. We say that an edge is monochromatic if the associated pair of colors are not different, otherwise the edge is bi-chromatic. Moreover, if $e$ is an edge incident to the vertices $v_i,v_j \in V(G)$ with $i<j$ and the associated ordered pair of colors to $e$ is $(c_1(e),c_2(e))$ then we say that $e$ is colored $c_1$ at $v_i$ and $c_2$ at $v_j$.

We will be interested in a special coloring of this graph:

**Inherited Vertex Coloring:** Let $G$ be a bi-colored weighted graph and $PM$ denote a perfect matching in $G$. We associate a coloring of the vertices of G with PM in the natural way: for every vertex $v_i$ there is a single edge $e(v_i) \in PM$ that is incident to $v_i$, let the color of $v_i$ be the color of $e(v_i)$ at $v_i$. We call this coloring $c$, the inherited vertex coloring (IVC) of the perfect matching PM.

**Weight of Vertex Coloring**: Let $G$ be a bi-colored weighted graph. Let $\mathcal{M}$ be the set of perfect matchings of $G$ which have the coloring $c$ as their inherited vertex coloring. We define the weight of $c$ as
$$w(c) := \sum_{PM \in \mathcal{M}} \prod_{e \in PM}w_e. $$
Moreover, if $w(c)$=1 we say that the coloring gets unit weight, and if $w(c)$=0 we say that the coloring cancels out.

Question: For which values of $n$ and $d$ are there bi-colored graphs on $n$ vertices and $d$ different colors with the property that all the $d$ monochromatic colorings have unit weight, and every other coloring cancels out?

We call such graphs monochromatic with respect to the IVC.

- The only known examples are $C_{2n}$ and $K_4$. Furthermore, Ilya Bogdanov has shown that, if all $w_e$ are positive real numbers, these examples are the only solutions.

**Example of Inherited Vertex Coloring:**
A bi-chromatic weighted edge with one double edge between vertex 4 and 6 is shown on the top left, the edge weights $E_{ij}$ are shown below. On the right top, its eight perfect matchings are shown, and $w(PM_i)$ denotes the product of the edge weights of the perfect matching $PM_i$. The perfect matching 4 and 5 have the same inherited vertex coloring. As $w(c)=w(PM_4)+w(PM_5)=0$, we say this coloring cancels out. There are six remaining IVCs with nonzero weights, three of them are monochromatic, while three others are non-monochromatic. Therefore, the graph is not monochromatic.

directed, i.e., that it is specified which its endpoint should get which color? Can some edge heve zero weight? $\endgroup$ – Ilya Bogdanov Oct 5 '18 at 16:26