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:

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

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

enter image description here

  • 2
    $\begingroup$ It is very hard to understand your intentions at the part labelled as "Cancellation of Perfect Matchings". Can you define precisely, (without an example!) what does it mean that two perfect matchings cancel out? As i understand the definition needs some kind of coloring, but it is not clear whether I can choose the coloring or is it done in a deterministic manner as in your first example? (The coloring is according to the unique triple of disjoint perfect matchings. But what about the other edges? etc.) $\endgroup$ Jun 6, 2018 at 12:46
  • $\begingroup$ @DanielSoltész Thank you for your comment, I tried to clearly state in words what it means. Could you please check whether this is clear now? Thank you a lot! $\endgroup$ Jun 6, 2018 at 17:43

1 Answer 1


Look at the strong product of an even complete graph with an even cycle, $G=K_{2n}\boxtimes C_{2m}$. We can give an edge coloring to this graph such that any vertex coloring is either not inherited from a perfect matching, or it is inherited by exponentially many matchings, and all monochromatic vertex colorings are induced from some perfect matching.

We can denote the vertices by pairs $(x,y)$ with $x\in \{1,2,\dots,2n\}$ and $y\in \mathbb Z/2m\mathbb Z$, so that we have edges $(x_1,y_1)\sim(x_2,y_2)$ iff $y_1-y_2\in \{-1,0,1\}$. We will pick the coloring of the edges as follows: the blue edges are all edges of the form $\left((x_1,y),(x_2,y)\right)$, the green edges are all edges of the form $\left((x_1,2y)(x_2,2y+1)\right)$, and the red edges are all edges of the form $\left((x_1,2y)(x_2,2y-1)\right)$.

For a given coloring, $C$, of the vertices of $G$ we let $C(b,y), C(g,y), C(r,y)$ denote the number of values of $x$ for which $(x,y)$ is colored blue, green, or red, respectively. It is easy to prove that $C$ is the inherited coloring of a perfect matching in $G$ iff

  • $C(g,2y)=C(g,2y+1)$ for all $y$
  • $C(r,2y)=C(r,2y-1)$ for all $y$
  • $C(b,y)$ is even for all $y$

in particular this is satisfied for all monochromatic colorings. Given such a coloring $C$, the number of perfect matchings that induce it is given by $$\prod_{y=1}^mC(g,2y)!C(r,2y)!\prod_{y=1}^{2m}(C(b,y)-1)!!$$ which is not only greater than 1, but grows like $e^{O(nm\log n)}$.

  • $\begingroup$ Great, that sounds quite interesting. While I try to understand it, could you give an concrete example, or (an upper limit of) the smallest number verticles $|V|$ where that might happen? thank you $\endgroup$ Sep 20, 2018 at 23:19
  • 3
    $\begingroup$ It already holds for $K_6\boxtimes C_4$ on 24 vertices with the coloring described above. $\endgroup$ Sep 20, 2018 at 23:23
  • $\begingroup$ I just understood what you constructed, and find it very beautiful. Thank you. I think in your final enumeration, one needs to be careful about the limits of $y$ in the multiplication (i think it should go from $y=1$ to $y=m$, not to 2m), otherwise one overcounts the solutions. Even if thats the case, you are right of course that every IVC appears exponentially often, and thereby answered my question. The connection to quantum physics needs to be specified now more careful, i need to restate the question in a more subtle way. Thank you very much! $\endgroup$ Sep 21, 2018 at 22:54
  • $\begingroup$ @NicoDean, thank you, I fixed the typo. $\endgroup$ Sep 21, 2018 at 23:06
  • $\begingroup$ I have specified the question in a follow-up question. Your answere here shows that graphs can exist which fulfill a necessary condition on my new question. $\endgroup$ Sep 24, 2018 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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