Let $\ M $ be a matching in a simple bi-partite undirected graph $\ G = (V,E) $ where $\ |V| = n $ and $\ |E| = m $ . The graph is represented by adjacency list. I need to prove or disprove that it can be checked wether $\ M $ is a maximum matching in $\ \Theta(n+m) $
I was thinking of turning the graph into a network with source and sink and then find minimum cut but it will be a problem computing the time complexity of such algorithm (if there's any?)
I'll give some hints without details. A matching $M$ is a maximum matching if and only if the graph has no alternating paths (with respect to $M$) ending in unmatched vertices. You can find such a path in linear time. If you prefer to think in terms of networks, you should use the fact that the flow is maximum if and only if there are no augmenting paths. I.e. you only have to run one iteration of the Edmonds-Karp algorithm to check whether a given flow is maximum.
EDIT: A standard way of finding an augmenting path in a bipartite graph $G = (A,B,E)$ is to orient the edges in $M$ from $A$ to $B$ and the rest of the edges from $B$ to $A$. Let $X,Y$ denote the set of unmatched verties in $A$ and $B$, respectively. Then the problem is to decide whether any vertex in $X$ is reachable from a vertex in $Y$ by a directed path. You can solve this by using standard graph traversal algorithms (e.g. BFS). A small trick to make this run in linear time is to add a new root vertex $v$ to the graph, along with edges $vy$ for every $y \in Y$ and start the search from this vertex.