On complexity of special maximum matchings constructing Original Research Article

For bipartite graphs the NP-completeness is proved for the problem of existence of maximum matching which removal leads to a graph with given lower(upper) bound for the cardinality of its maximum matching.