Abstract: The new maximum matching graph $\mathcal{NM}(G)$ of a graph $G$ is a graph where vertices are maximum matchings of $G$ and two maximum matchings $M_{1}$ and $M_{2}$ are adjacent in $\mathcal{NM}(G)$ if the symmetric difference of $M_{1}$ and $M_{2}$ induces a path (there is no limit for the length of the path). In the paper, we study the connection of new maximum matching graph, and the necessary and sufficient condition of the new maximum matching graph being a complete graph or a tree or a cycle are obtained, respectively.

Key words: maximum matching, new maximum matching graph, factor-critical graph, bipartite graph with positive surplus