Each vertex in a graph is randomly and independently colored either red or blue with equal probability.
A coloring is called **$r$-good**, for some fraction $r\in[0,1]$, if at least a fraction $r$ of the edges touch at least one red vertex.
Define $p(G,r)$ as the probability that a graph $G$ is $r$-good. Obviously $p(G,r)$ is decreasing with $r$.

**What is the largest $r$ such that $p(G,r)>1/2$ for all finite graphs $G$?**

There is an upper bound of $2/3$ (as noted by Kevin P. Costello) and a lower bound of $1/2$.

For the upper bound, let $G$ be the clique with $3$ vertices. It has eight different colorings: one is 0-good, three are 2/3-good and four are 1-good. Therefore, $p(G,2/3)= 7/8$, but for every $r>2/3$, $p(G,r)\leq 1/2$.

For the lower bound, consider an arbitrary graph $G$. For every coloring of $G$, either it or its opposite colorng is $1/2$-good; therefore $p(G,1/2)\geq 1/2$. To prove that $p(G,1/2)>1/2$, it is sufficient to prove the existence of a coloring that both it and its opposite are $1/2$-good. To construct such a coloring, assign a unique number to each vertex of $G$, and assign to each edge $(u,v)$ the number $(u+v)/2$. Let $D$ be the median of all edges' numbers. Color all vertices smaller than $D$ red and all other vertices blue. Both this coloring and its opposite are $1/2$-good. Hence $p(G,1/2)>1/2$.

Intuitively, the 3-clique seems to be the worst case, since when there are many vertices, the expected number of good edges is $3/4$. So my conjecture is that the real value is 2/3. In other words:

**Conjecture.** For every finite graph $G$, $p(G,2/3)>1/2$.

Is this true? Alternatively, can you prove tighter bounds?