# Why is bipartite graph matching hard?

I am reading on how solving maximum flow (Ford-Fulkerson) can be also used to solve unweighted bipartite graph matching problem. I think I don't understand the essence of this problem, because to me it seems trivial.

The method of solving the problem says to convert the original bipartite graph into a network, by creating a Source and Sink vertices, directing all edges towards the Sink and setting all edges' capacity to 1. Then I should run Ford-Fulkerson. Fair enough.

My question is, can't I just do this linearly? (Obviously not, but I don't see why). The goal of the problem seems to be to find a maximum matching in a complete bipartite graph - i.e. the maximum number of edges between the two "sections" of the graph that do not share any vertices.

To illustrate, see this picture • In the first graph the maximum matching will be 2 - any of the two vertices on the right may only be connected to a single vertex on the left. Since the edges are unweighted, it doesn't really matter which?
• Similarly in the second graph, the matching will again be just 2.

Can you tell me where am I thinking wrong? I don't understand where the complexity of the problem comes from.

And sorry if any of the terms were used incorrectly, I am not studying CS in English. Thanks

• Do you realize that not all vertices on the right need to be connected to all vertices on the left? (then it will still be a bipartite graph). edit: I see now that you say "complete bipartite graph". Then your solution would be correct. – Albert Hendriks Jun 1 '16 at 19:34
• It might also be that the input is guaranteed to be a (complete) bipartite graph, but that your algorithm just needs to figure out how many nodes are on the left and how many on the right. – Albert Hendriks Jun 1 '16 at 19:56