### @Busybee_mou's approach to a graph theory puzzle

Here's the original tweet thread:

Select a random subset such that each is chosen with probability , independently.

An edge is

*crossing*if it is between vertices and such that precisely one of and is in .Let be the subset of all vertices not in such that has NO friend (I mean neighbour) in . Clearly then the union is a subset for which, every vertex not in has a friend in . Note that

What is ?

Â

## [Turns out to be , reveal toggle to see why.]

For a vertex to be in (keep in mind that as is random, too is a random subset), it must be the case that neither not ANY of its friends has been chosen to be included in

If denotes the number of friends of, then:

Via linearity of expectations, we get:

,

since .

Thus:

Â

So now, we have to minimize the function over . We have , which is increasing as long as and decreasing as long as . Thus, the minimum is attained at . This yields:

Â

A different way of selecting . Suppose we fix p and we select uniformly randomly out of all possible subsets of cardinality of . Define the same as before. For to be in , neither nor any of its friends can be included in , which means that in that case must have been chosen from among subsets of cardinality of , where indicates the set of all friends of . Thus:

This actually gives only a slight improvement over the previous bound, and this improvement becomes insignificant for large.