Using your Head is Permitted

Every Christmas, the employees of MegaCorp play a gift-giving lottery game. On the first of December, each of the company's N employees picks a number between 1 and N out of a hat (the same hat) to be their unique ID number in the game. On Christmas day, each employee sends a gift to the person who has the highest ID number among all employees who are directly connected to them on LinkedIn. We consider every employee to be connected to herself, so if every one of an employee's connections has a lower ID number than herself, that employee will be sending a self-addressed Christmas present.

The question:
Prove that for no connected graph of LinkedIn connections (with more than a single employee) this game ends up with more than 3/4 of the employees receiving gifts, in expectation. (Bonus for proving tighter bounds.) The order of the IDs is taken here to be random and uniformly distributed among all N! possibilities.

Note that in a valid graph of LinkedIn connections, for any i and j, if i is connected to j then j is connected to i.

List of solvers: