  Krenn, Gu and Zeilinger initiated the study of PMValid edge-colourings
because of its connection to a problem from quantum physics. A graph is defined
to have a PMValid $k$-edge-colouring if it admits a $k$-edge-colouring (i.e. an
edge colouring with $k$-colours) with the property that all perfect matchings
are monochromatic and each of the $k$ colour classes contain at least one
perfect matching.
  The matching index of a graph $G$, $\mu(G)$ is defined as the maximum value
of $k$ for which $G$ admits a PMValid $k$-edge-colouring. It is easy to see
that $\mu(G)\geq 1$ if and only if $G$ has a perfect matching (due to the
trivial $1$-edge-colouring which is PMValid). Bogdanov observed that for all
graphs non-isomorphic to $K_4$, $\mu(G)\leq 2$ and $\mu(K_4)=3$. However, the
characterisation of graphs for which $\mu(G)=1$ and $\mu(G)=2$ is not known. In
this work, we answer this question. Using this characterisation, we also give a
fast algorithm to compute $\mu(G)$ of a graph $G$. In view of our work, the
structure of PMValid $k$-edge-colourable graphs is now fully understood for all
$k$. Our characterisation, also has an implication to the aforementioned
quantum physics problem. In particular, it settles a conjecture of Krenn and Gu
for a sub-class of graphs.
