Homework 5

1.  There is only one stable matching.  If all individuals have the same preferences then the two most favored individuals will match, the second most preferred individuals will match, etc., resulting in a unique solution.

2. 
                     O
                  /     \
                /         \
              /             \
            O                 O
          /   \             /   \
         O     O           O     O
       /   \ /   \       /   \ /   \
     O     O O     O   O     O O     O

a) Yes, all trees are bipartite

b)   \\ = matched edges
                     O
                  /     \\
                /         \\
              /             \\
            O                 O
          /   \             /   \
         O     O           O     O
       /  \\  /  \\     /   \\  /  \\
     O     O O     O   O     O O     O

c) 5 vertices = X

                     X
                  /     \
                /         \
              /             \
            O                 O
          /   \             /   \
         X     X           X     X
       /   \ /   \       /   \ /   \
     O     O O     O   O     O O     O

3. 

     O --- O
   /         \
  O           O
   \         /
     O --- O 

a) Yes, no odd cycle

b) 

     O --- O
   /         \\
  O           O
  \\         /
     O --- O 

c)  

     O --- O
             \\
  O           O
            /
     O     O