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 IVC equal 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.