A bipartite graph can be divided into two sets of nodes where all edges have one end in each. The graph must be undirected. In a matching, no element of a set may appear in more than one pair ( each node may appear in at most one edge). Perfect edge means exactly one edge for every node(no disconnected nodes). These concepts are firmly imbued with Network Flow. We will use concepts shown by Network Flow to attempt to solve the problem: What is the size of the largest matching in a some bipartite graph G? As we will learn, this problem requires advanced techniques to solve which we have not yet covered.

First, we need to understand the basics of flow networks. Flow is what travels along the edges in a flow network between nodes. Each edge has a capacity Ce representing the maximum amount of flow that it can transport. Further, flow networks must have two special nodes: a source node which the original flow comes from and a sink node which is the final node receiving the flow(takes all that is transported through). There are several required conditions for a graph to represent a flow network. No node may exceed its capacity(capacity condition) and the amount of flow from a given edge cannot exceed the amount of flow into it(conservation condition). The maximum flow problem involves finding a flow of maximum possible value in some flow network. To solve this, we will focus on how some node's capacities put bounds on flow. A “cut” of a flow network is basically just a path that some quantity of flow follows between nodes from source to sink.