Randomized Algorithms 8 (c) is too hard

[mohit-rajpal]

When I proposed my solution to this problem, I was not sure whether the proof given by the TA did not result in a logical contradiction. Can it be upgraded to be slightly more than a small star?