1.  a) 6
    b)

             3        2/4
         s<-------a<------->b
         ^        ^         ^
         |        |1/1      |4
         |3       |         |
         |  2/3   v    2    |
         c<------>d<--------t

Notation of x/y means x to right and y to left (or x up and y down)

2. 

The left side has n items, and the right side has n items, each labeled 1-n.

The 1st node on the left connects to every node on the right (1,2,...n) and in that order.
The 2nd node on the left connects to every node on the right except for n (1,2,...,n-1) in that order
And so on..
The nth node on the left connects only to node 1 on the right.

When this algorithm runs, the 1st node will try to visit 1 first.  The second will visit 2, etc...
Eventually, this pairing will fail.  We'll backtrack and eventually the second node will try to visit node #3 (after trying all combinations with it pointing to node 2).  This pairing eventually fails but only after trying (n-1)(n-2)...(1) combinations.

We repeat this again where the 1st node visits the second node.  This again fails with (n-1)! attempts.

As you can see, this will take n! steps to get the one we want.  theta(n!) = O(2^n) and is exponential.