2. A bipartite graph that doesn't have a matching might still have a partial matching. By this we mean a set of edges for which no vertex belongs to more than one edge (but possibly belongs to none). Every bipartite graph (with at least one edge) has a partial matching, so we can look for the largest partial matching in a graph. Your "friend" claims that she has found the largest partial matching for the graph below (her matching is in bold). She explains that no other edge can be added, because all the edges not used in her partial matching are connected to matched vertices. Is she correct? 3. One way you might check to see whether a partial matching is maximal is to construct an alternating path. This is a sequence of adjacent edges, which alternate between edges in the matching and edges not in the matching (no edge can be used more than once). If an alternating path starts and stops with an edge not in the matching, then it is called an augmenting path. (a) Find the largest possible alternating path for the partial matching of your friend's graph. Is it an augmenting path? How would this help you find a larger matching? b) Find the largest possible alternating path for the partial matching below. Are there any augmenting paths? Is the partial matching the largest one that exists in the graph? 4. The two richest families in Westeros have decided to enter into an alliance by marriage. The first family has 10 sons, the second has 10 girls. The ages of the kids in the two families match up. To avoid impropriety, the families insist that each child must marry someone either their own age, or someone one position younger or older. In fact, the graph representing agreeable marriages looks like this The question: how many different acceptable marriage arrangements which marry off all 20 children are possible? (a) How many marriage arrangements are possible if we insist that there are exactly 6 boys marry girls not their own age? of marriage arrangements? Look at smaller family sizes and get a sequence (b) Could you generalize the previous answer to arrive at the total number (c) How do you know you are correct? Try counting in a different way. (d) Can you give a recurrence relation that fits the problem? 5. We say that a set of vertices A V is a vertex cover if every edge of the graph is incident to a vertex in the cover (so a vertex cover covers the edges) 2. A bipartite graph that doesn't have a matching might still have a partial matching. By this we mean a set of edges for which no vertex belongs to more than one edge (but possibly belongs to none). Every bipartite graph (with at least one edge) has a partial matching, so we can look for the largest partial matching in a graph. Your "friend" claims that she has found the largest partial matching for the graph below (her matching is in bold). She explains that no other edge can be added, because all the edges not used in her partial matching are connected to matched vertices. Is she correct? 3. One way you might check to see whether a partial matching is maximal is to construct an alternating path. This is a sequence of adjacent edges, which alternate between edges in the matching and edges not in the matching (no edge can be used more than once). If an alternating path starts and stops with an edge not in the matching, then it is called an augmenting path. (a) Find the largest possible alternating path for the partial matching of your friend's graph. Is it an augmenting path? How would this help you find a larger matching? b) Find the largest possible alternating path for the partial matching below. Are there any augmenting paths? Is the partial matching the largest one that exists in the graph? 4. The two richest families in Westeros have decided to enter into an alliance by marriage. The first family has 10 sons, the second has 10 girls. The ages of the kids in the two families match up. To avoid impropriety, the families insist that each child must marry someone either their own age, or someone one position younger or older. In fact, the graph representing agreeable marriages looks like this The question: how many different acceptable marriage arrangements which marry off all 20 children are possible? (a) How many marriage arrangements are possible if we insist that there are exactly 6 boys marry girls not their own age? of marriage arrangements? Look at smaller family sizes and get a sequence (b) Could you generalize the previous answer to arrive at the total number (c) How do you know you are correct? Try counting in a different way. (d) Can you give a recurrence relation that fits the problem? 5. We say that a set of vertices A V is a vertex cover if every edge of the graph is incident to a vertex in the cover (so a vertex cover covers the edges)