The following purely graph-theoretic question is motivated by quantum mechanics.

**Definitions**: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be monochromatic or bi-chromatic. The later means that the two endpoints of an edge are allowed to have different colors.

We will be interested in perfect matchings of bi-colored graphs. If $G$ is a bi-colored graph and *PM* is a perfect matching in $G$ then we can associate a coloring of the vertices of $G$ to the matching *PM* in the natural way: every vertex gets the color of the edge of *PM* that is incident to said edge. (Note that a red-blue bi-chromatic edge of *PM* results in one endpoint of this edge being colored red but the other one blue.) We call these associated (inherited) colorings the *inherited vertex coloring* (*IVC*) of the perfect matching *PM*.

Question: Is there a bi-colored graph with $|V|>4$ with the following properties:

For all three colors (red, green, blue) there is at least one perfect matching that has a monochromatic

IVC.For every non-monochromatic vertex coloring $c$, there is either no perfect matching of $G$ that has its

IVCequal to $c$, or there are at least two such perfect matchings.

- The special case for graphs with no non-monochromatic IVC has been solved by Ilya Bogdanov.
- The connection to quantum mechanics is described in this article (where I also cite Ilya's solution at MO).

**Example of Inherited Vertex Coloring:**

Here I show an example Graph with 8 vertices, with monochromatic and bichromatic edges. It has 7 perfect matchings. For each of the three colors red, blue and green, there is exactly one perfect matching with a monochromatic *IVC* (PM1-3).

For the coloring ($g$=green, $b$=blue, $r$=red) $c=ggggbbbb$, there are two PMs with that IVC (PM4 and PM6) - this is property 2.

However, for the non-monochromatic vertex coloring $c=bbbbgggg$ and $c=rgggbrrr$, there is exactly one such perfect matching with this IVC - this the graph $G(V,E)$ does not have the required property.