We consider the problem of finding in a graph a set $R$ of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with $n$ nodes on each side, we give sufficient conditions for the existence of a set $R$ with $|R| = n + 1$ such that perfect matchings with $k$ red edges exist for all $k, 0\le k\le n$. Given two integers $p<q$ we also determine the minimum cardinality of a set $R$ of red edges such that there are perfect matchings with $p$ red edges and with $q$ red edges. For 3-regular bipartite graphs, we show that if $p\le 4$ there is a set $R$ with $|R| = p$ for which perfect matchings $M_k$ exist with $\vert M_k\cap R\vert\le k$ for all $k\le p$. For trees we design a linear time algorithm to determine a minimum set $R$ of red edges such that there exist maximum matchings with $k$ red edges for the largest possible number of values of $k$.