In this lesson, we'll study bipartite graphs, and again we'll start with a problem. Our school has four job openings, administrator, programmer, librarian, and professor. And there are four people who applied for these jobs, can we fill all the positions? Alice wants to be either an administrator or librarian, Ben wants to be programmer or a librarian. Chris can do administrator or programmer's jobs, and Diana only wants to be a professor. Let us first draw the following graph. It will be a bipartite graph where the left-hand side we'll have four vertices corresponding to job openings. And on the right side, we'll have four vertices corresponding to four people. A means Alice, B Ben, C Chris, and D Diana. Now I connect a job opening with a person if and only if this person wants to do this job. Here's what it looks like. For example, Alice only wants to be administrator or librarian, so I have two edges going from the vertex A. So now I want to find four edges in this graph such that they cover all the vertices on the left. And they don't share vertices on the right. So we want to find four disjoint edges. Clearly, only Diana can be professor, so we'll hire her for this position. Now we want to assign distinct jobs to those three people. Again, this means that we want to find one edge going from the administrator position, one edge from programmer, one edge from librarian. Such that they all end in different positions on the right, at different vertices on the right-hand side. So we want to find three disjoint edges in the remaining graph. We can do this, this is a solution. We found a solution for the original problem. Now let's solve a similar problem. There are six students and there are six single rooms in dorm room. Can we find a room assignment such that everyone lives in a room he likes? For example, Aaron only likes rooms 1 and 2. Bianca only likes the first three rooms, and the remaining preferences you can see on the screen. We want to find such a room assignment that everyone likes her room. Again, let's draw a bipartite graph. On the left side, we have six vertices corresponding to six people. And on the right side, we have six vertices for rooms from 1 to 6. Again, we draw an edge between a person and room if this person likes the room. For example, Aaron only likes the rooms number 1 and 2, so there are two edges going from A. They go to the vertices 1 and 2 on the right side. Can we find such a solution? No, let's look at Carol, Emma, and Francis. Three of them like only two rooms, rooms number 4 and 5. Since each of these rooms can only fit one person, there is no room assignment which would satisfy Carol, Emma, and Francis. This means there is no room assignment for all six people either, so there is no ideal solution. Later in this lesson we will see that actually, this is the only situation which can prevent us from finding an ideal assignment.