$\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\E}{\mathbb E}$
The Problem
Let $G=(V, E)$ be a (finite, simple) graph. Let $\chi:V\to \set{R, B}$ be a $2$-coloring of $V$. We say that a vertex $v\in V$ is $\chi$-good if the number of neighbors of $v$ which get the same color as $v$ is no more than the number of neighbors of $v$ which get different color than $v$. In other words, $$ |\set{u\in N(v):\ \chi(u) = \chi(v)}| \leq |\set{u\in N(v):\ \chi(u)\neq \chi(v)}| $$ where $N(v)$ is the set of all the neighbors of $v$. A $2$-coloring $\chi$ is said to be admissible if each vertex $v\in V$ is $\chi$-good.
Consider the following problem.
Problem. Show that every graph admits an admissible $2$-coloring.
A proof of this problem can be given as follows. Given a $2$-coloring $\chi$ of $G$, we call an edge nice if the endpoints of this edge have different colors. Choose a $2$-coloring $\chi_0$ of $V$ which has the maximum number of nice edges. We claim that any such coloring is admissible. To see this, assume on the contrary that $\chi_0:V\to \set{R, B}$ is not admissible. So there is a vertiex $v$ whihc is not $\chi_0$-good. But now flipping the color of $v$ increases the number of nice edges, producing a coloring which has more nice edges than present in $\chi_0$. This contradicts the maximality assumption.
The Probabilistic Argument
However, I would like to see how much can we get out of a probabilistic argument. The following argument shows that there exists a $2$-coloring which has at least $|V|/2$ good vertices.
Color each vertex independently red or blue with probability $1/2$. So we can now talk about a random coloring. For each $v\in V$, let $G_v$ be a random variable valued in $\set{0, 1}$ which takes the value $1$ if $v$ is good, otherwise it takes the value $0$. Clearly, $P[G_v=1]=1/2$, because a vertex will be good of not good with equal probability. Therefore, $\E[G_v]=1/2$, and hence, by linearity of expectation, we have $\E[\sum_{v\in V} G_v]=|V|/2$. This means that there must exist a coloring where we have at least $|V|/2$ good vertices.
Question. How much further can we take this? Can we show, for instance, that there must exist a coloring with at least $3|V|/4$ good vertices via a probabilistic approach too?