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
I am reading on how [...] to solve unweighted bipartite graph matching problem. [...] The goal of the problem seems to be to find a maximum matching in a complete bipartite graph


No, the goal of the problem is to find a maximum matching in any unweighted bipartite graph.