To see this, consider a relaxation of the original problem where we omit the
requirement for the graph to be connected. Now, add *M* isolated vertices.
By taking *M* to infinity (and dividing each number in the hat by
*N*+*M*), the original rules of the game become the new ones. Clearly,
the addition of the isolated vertices does not affect the question of which of
the original *N* players received a present, so we can safely ignore them.

With these new rules, let us now begin by proving the 0.75 bound.

Consider how many presents are sent to employees
whose ID is in the range [0,0.5]. For such a present to be sent, both the
sending employee and all of her LinkedIn connections (of which there is at least
one) must have IDs in this same range. The expected number of such presents
is therefore never more than *N*/4. This being the number of such presents,
clearly the number of employees whose number is in this range who
*receive*
presents cannot be larger. Even if all other employees receive presents, there
is only an expected *N*/2 of them, leading to the desired
3/4 *N* upper bound in total.

(I will remark at this point that all the correct solutions I've seen make,
at some point, this leap between "expected number of presents" and
"expected number of employees". The majority of *incorrect* solutions
this month try to prove exactly the same claim but going directly for the
number of gift-receiving employees, and, in order to do so, invariably rely on
incorrect steps in the probabilistic rationale.
In this particular case both camps tended to reach
the same conclusion, but it is not difficult to construct a question where this
particular type of derivation error leads to incorrect results.)

To get to a bound tighter than 3/4, consider that the 3/4 *N* bound
required every
employee to have only one LinkedIn connection. For any employee with *d*
LinkedIn connections, the probability that this employee will be sending out a
present to someone whose ID is in [0,0.5] drops from 1/4 to
2^{-(d+1)}. On the other hand, for any employee with *d*
LinkedIn connections, the probability that this particular employee will
*receive* a present is never more than *d*/(*d*+1), because
there is a 1/(*d*+1) chance that this employee will have a lower ID than
any of its connections, a case in which the employee will surely not receive
any present.
In a situation where (almost) all employees have exactly one
connection, the upper bound is therefore really 1/2.

One can therefore take *p*_{1} to be the percentage of employees
who have exactly one connection, and calculate the two bounds above given
*p*_{1}. The real bound would be the minimum of the two bounds,
and the best bound is the maximum value of this minimum over the entire range
of possible *p*_{1} values. This happens to be when the two
bounds are equal to each other.

This leads to the equation

The 0.7 bound can be improved further, by noting that the original threshold
value picked (0.5) is not necessarily optimal. Whereas 0.5 was optimal for the
original choice *p*_{1}=1, for a general *p*_{1}
value we can do better. Optimally, one counts the number of presents sent to
people with ID *x* for those *x* values that receive less than one
present, in expectation, and one counts the people (whether or not they receive
presents), otherwise. This makes the bound tighter.

A final improvement can be done by parameterizing also by the percentage of
employees with other *d* values. This adds infinitely many parameters
*p _{d}* that need to be optimized, but using Lagrange multipliers
it is possible to show that at most 2 of them can be nonzero at the optimum.
Add to this the fact that they need to sum to 1, and we have only two
parameters to play with:

Putting all this together, the best upper bound I know of is approximately 0.63319213231789395, which is about midway from the original 3/4 bound to the highest-value graph that I've been able to construct, and is a marginal improvement over the 2/3 bound. (The best graph will be given in the Ponder This solution.)