Please go through the video first. It may be difficult for the students to find out the correct reduction, so it is more important to identify and disprove a wrong reduction. For the correct reductions, put emphasis on the reduction lemma and proving both sides (for the incorrect reductions, ask the students to determine which side of the correctness lemma can be proven and which cannot be).

1. Reduce 3SAT to 4SAT.

Same idea as in 2SAT to 3SAT reduction.

2. Consider this reduction:

def myreduce(G,s,t): // G is a directed graph and s and t are its vertices
  construct empty undirected graph H
  add node sout and tin to H
  for every node v in G:
    add nodes vout and vin to H
    add edge vin-vout to H
  for edge u -> v in G:
    add edge uin-vout to H

We want to investigate if myreduce() is a polynomial-time many-one reduction from UndirectedHamPath to DirectedHamPath?
(a) State the correctness lemma assuming that myreduce is a correct reduction.
(b) Try to prove both the directions of the lemma. Which side can you prove? 
(c) Which side you are unable to prove and why? Come up with a counter-example based on why the proof fails for one side.
(d) Suggest a correct reduction.
Hint: Add two edges between u and v in the reduced graph for any edge u-v in the original graph.

3. Use idea from (2) to design a reduction from DirectedHamPath to UndirectedHamPath.

4*. Reduce 4SAT to 3SAT. (Standard idea -- available on web).
5*. Reduce 3SAT to VertexCover (VC). VertexCover takes as input a graph G and an integer k and decides if G has a vertex cover of at most k vertices. A vertex cover of a graph is a subset of vertices V' such _every_ edge in G has one or both end-points in V' (so, all edges are "covered" by some vertex in V'). This reduction uses similar idea as in the 3SAT to IS reduction. 

Hint: Think of 3SAT as "Is there a way to select at most 2m literals s.t. no variable and its negation are selected, and at most 2 literals in every clause are _not_ selected?" and VC as "Is there a way to select at most k vertices such that for no edge, both its endpoints are _not_ selected?"