(Solved): The figure below shows a bipartite graph with all edges connecting a node from \( A=\{1,2,3,4\} \) ...

The figure below shows a bipartite graph with all edges connecting a node from \( A=\{1,2,3,4\} \) to a node from \( B=\{5,6,7\} \). The edges in the graph are \( \{(1,5),(1,6),(2,6),(3,6),(3,7),(4,5)\} \), where \( M=\{(1,5),(3,6)\} \) is the set designated as matching edges. (a) Starting from an exposed node in \( A \), find an alternating path to an exposed node in \( B \). (If necessary, see Goemans' notes as above.) Clearly show your alternating path. (b) Use your alternating path to augment the matching. (c) Explain how you know that the matching is now maximum. (d) Find a node cover (that is, a set of nodes that covers all the edges) that has the same size as the maximum number of matching edges (three). \[ [2+2+2+2=8 \text { marks }] \]