Number of vertices present in all maximum matchings Given a graph $G$, we need to find the cardinality of the largest set of vertices so that each of them are present in every maximum matching possible. 

Is there a solution beside the obvious remove each vertex and find the maximum matching to see it reduces?
Is your graph bipartite? Because, if it is: suppose that one side of the bipartition is left and the other is right. Find a maximum matching, and orient all matched edges left-to-right and all unmatched edges right-to-left. Then a vertex $v$ can be omitted from a maximum matching if and only if one of the three following (mutually exclusive) conditions holds:


$v$ is already unmatched
$v$ can be reached from an unmatched vertex on its side of the bipartition in the resulting digraph
$v$ can reach an unmatched vertex on its side of the bipartition in the resulting digraph.


By doing two breadth-first or depth-first searches, one to find the parts of the graph that can be reached from unmatched vertices and one to find the parts that can reach unmatched vertices, you can find the essential vertices in linear time once you already have the matching.

Probably something like this will also work for the non-bipartite case, using a blossom-contracting alternating path search, but the details will be more complicated.