1 Five film studies students need to review five different films for an assignment, but only have one evening left before the assignment is due in. They decide that they will share the work out so that each of them reviews just one film. Jack \(( J )\) wants to review a horror movie; Karen \(( K )\) wants to review an animated film; Lee \(( L )\) wants to review a film that is suitable for family viewing; Mark ( \(M\) ) wants to review an action adventure film and Nikki ( \(N\) ) wants to review anything that is in 3D. The film "Somewhere" ( \(S\) ) has been classified as a horror movie and is being shown in 3D; "Tornado Terror" ( \(T\) ) has been classified as an action adventure film that is suitable for family viewing; "Underwater" \(( U )\) is an animated action adventure film; "Vampires" ( \(V\) ) is an animated horror movie that is suitable for family viewing and "World" ( \(W\) ) is an animated film.

1. Draw a bipartite graph to show which student ( \(J , K , L , M , N\) ) wants to review which films ( \(S , T , U\), \(V , W\) ). Initially Jack says that he will review "Somewhere", Karen then chooses "Underwater" and Lee chooses "Tornado Terror", but this would leave both Mark and Nikki with films that they do not want.
2. Write down the shortest possible alternating path starting from Nikki, and hence write down an improved, but still incomplete, matching.
3. From this incomplete matching, write down the shortest possible alternating path starting from "World", and hence write down a complete matching between the students and the films.
4. Show that this is the only possible complete matching between the students and the films.