to q in da ( I 0 ); otherwise , p is single in da ( I 0 ). Hints : ( 1 ) Use the confluence property of the deferred acceptance algorithm ; ( 2 ) Observe that once execution of the deferred acceptance algorithm reaches a state where there is exactly one single man who has not proposed to all of his acceptable women , the rest of the execution is deterministic . Definition : For any SMI instance I and any woman q in I , we define the unique element x identified in Problem 1 as threshold ( I , q ). Problem 2 . Let I be an SMI instance , let q be a woman in I , let p be a man who is not in I , and let I 0 be an SMI instance in add ( I , p , q ). Prove that no woman q 0 in I prefers threshold ( I , q 0 ) to threshold ( I 0 , q 0 ). Hints : ( 1 ) Use proof by contradiction , i . e ., assume that there is a woman q 0 who prefers threshold ( I , q 0 ) to threshold ( I 0 , q 0 ), and derive a contradiction ; ( 2 ) Use the confluence property of the deferred acceptance algorithm . Problem 3 . Let I be an SMI instance , let q be a woman in I , let p be a man who is not in I , and let I 0 be an SMI instance in add ( I , p , q ). Prove that if p is single in 2 University of Texas at Austin Department of Computer Science Algorithms and Complexity CS 331 , Spring 2017 da ( I 0 ), then threshold ( I 0 , q 0 ) = threshold ( I , q 0 ) for every woman q 0 in I . Hints : ( 1 ) Use proof by contradiction , i . e ., assume p is single in da ( I 0 ) and there is a woman q 0 such that threshold ( I 0 , q 0 ) 6 = threshold ( I , q 0 ), and derive a contradiction ; ( 2 ) Use the result of Problem 2 ;