First, remark that a graph with maximum degree $\Delta$ can be properly (vertex)-colored using no more than $\Delta + 1$ colors. Indeed, simply order the vertices arbitrarily and assign to each vertex a color different from those assigned to any of its neighbors that have already been encountered. Since the latter constitute a set of size at most $\Delta$, one of our $\Delta + 1$ colors will always do the trick. Thus our resulting graph $G$ can be properly $6$-colored. Now, choose $3$ colors from the $6$ uniformly at random (so that all triples are equally likely) and collapse them into a single color - say red. Collapse the remaining $3$ colors into a single, different color - call this one blue. Then our original $6$-coloring induces a (likely improper) red-blue coloring of the vertices of $G$. The probability that any particular edge of $G$ is monochromatic with respect to this coloring is \[\frac{2 \cdot 4}{\binom{6}{3}} = 2/5\] so that the expected number of monochromatic edges under this coloring is most $2|E|/5$. Then there must exist some particular choice of partition (ergo, 2-coloring) for which no more than $2/5$ of the edges of $G$ are monochromatic - that is to say, at least $3/5$ of the edges of $G$ have endpoints of different colors.

Can someone clarify this collapsing into a single color idea?

A good idea, but it's not clear if it could be saved. For example: Quote: ...Now, choose $3$ colors from the $6$ uniformly at random (so that all triples are equally likely) and collapse them into a single color What does it mean and is it possible at all to do it? One should be careful when using probabilistic arguments.

Put $n$ instead $2004$. Simply stated, we have a graph $G(V,E)$ with $n$ vertices, each vertex has degree at most $5$. We want to cut the vertices $V$ into two parts $A,B$ such that the number of cross edges (that connect $A$ with $B$) is at least $\displaystyle\frac{3}{5}|E|$. Let the cut $(A,B)$ be the one that attains the maximal number of cross edges. For any vertex $v\in V$ by $d_c(v)$ we denote the number of edges incident with $v$ that are cross edges and $d_{in}(v):= d(v)-d_c(v)$ be the number of edges that connect $v$ with the vertices of the same part where $v$ is. The following properties hold: 1) For any vertex $v\in V$ $d_c(v)\geq d_{in}(v)$ 2) Suppose $a\in A$ is a vertex such that $d_c(a)=d_{in}(a)$. Let $b\in B$ and $ab$ is an edge in $G$. Then $d_c(b)-d_{in}(b)\geq 2$. For the first part, indeed, if it's false, we can transfer $v$ from the part it belongs, say $A$, to the other part $B$ and thus increase the number of cross edges. For the second part, assuming it doesn't hold and swapping $a$ and $b$ we get a configuration with bigger number of cross edges, a contradiction. Further, let $A_1:=\{a\in A:d_c(a)=d_{in}(a)\}$ and $B_1:=\{b\in B:d_c(b)=d_{in}(b)\}$. Denote by $B'_1$ the set of all vertices in $B$, $A_1$ is connected with. Respectively $A'_1$ be all vertices in $A$, each of them is connected with a vertex in $B_1$. The remaining vertices in $A$, resp. $B$ we denote as $A_2$, resp. $B_2$. By the second property, there do not exist edges between $A_1$ and $B_1\cup B_2$. For $a\in A'_1$, it holds $d_c(v)\geq d_{in}(v)+2$. Since $d(v)\leq 5$ it follows $\displaystyle d_c(v)\geq \frac{3}{4} d(v)$. The same is true for any vertex in $B'_1$. For any vertex $v\in A_2$ it holds $\displaystyle d_c(v)\geq \frac{3}{5} d(v)$. Now, let us estimate the number $c$ of cross edges between $A$ and $B$. $$\displaystyle c=\sum_{v\in A_1}d_c(v)+\sum_{v\in A'_1}d_c(v)+\sum_{v\in A_2}d_c(v)$$$$c\geq \frac{1}{2}\sum_{v\in A_1}d(v)+\frac{3}{4}\sum_{v\in A'_1}d(v)+\frac{3}{5}\sum_{v\in A_2}d(v).$$The same is true when cross edges are counted with respect to $B$. $$c\geq \frac{1}{2}\sum_{v\in B_1}d(v)+\frac{3}{4}\sum_{v\in B'_1}d(v)+\frac{3}{5}\sum_{v\in B_2}d(v).$$thus $$(1)\,\,\,\,\,\,\,\,\,\, c\geq \frac{1}{4}\sum_{v\in A_1\cup B_1}d(v)+\frac{3}{8}\sum_{v\in A'_1\cup B'_1}d(v)+\frac{3}{10}\sum_{v\in A_2\cup B_2}d(v).$$The number of all edges is $$(2)\,\,\,\,\,\,\,\,\,\,|E|= \frac{1}{2}\sum_{v\in A_1\cup B_1}d(v)+\frac{1}{2}\sum_{v\in A'_1\cup B'_1}d(v)+\frac{1}{2}\sum_{v\in A_2\cup B_2}d(v).$$By counting edges between $A_1$ and $B'_1$ it follows $$\displaystyle \frac{1}{2}\sum_{v\in A_1}d(v)\leq \frac{3}{4}\sum_{v\in B'_1}d(v)$$or $$\displaystyle \sum_{v\in A_1}d(v)\leq \frac{3}{2}\sum_{v\in B'_1}d(v)$$Similarly $$\displaystyle \sum_{v\in B_1}d(v)\leq \frac{3}{2}\sum_{v\in A'_1}d(v)$$and $$(3)\,\,\,\,\,\,\,\,\,\,\displaystyle \sum_{v\in A_1\cup B_1}d(v)\leq \frac{3}{2}\sum_{v\in A'_1\cup B'_1}d(v)$$Now look at $\displaystyle \frac{c}{|E|}$ as presented in $(1)$ and $(2)$ and as a function of $\displaystyle \sum_{v\in A_1\cup B_1}d(v)$, all other sums fixed. It attains it's minimal value when $\displaystyle \sum_{v\in A_1\cup B_1}d(v)$ is as large as possible. Hence, by $(3)$: $$\frac{c}{|E|}\geq \left(\frac{3}{4}\sum_{v\in A'_1\cup B'_1}d(v)+\frac{3}{10}\sum_{v\in A_2\cup B_2}d(v)\right) / \left(\frac{5}{4} \sum_{v\in A'_1\cup B'_1}d(v)+ \frac{1}{2}\sum_{v\in A_2\cup B_2}d(v)\right).$$It means $\displaystyle \frac{c}{|E|}\geq \frac{3}{5}.$

Group vertices with the same color under a set. Let $A,B$ be the sets produced this way. For each $v\in A$ let $d^+(v)$ be the number of edges from $v$ contributing to the total count of crossing edges, and $d^-(v)$ the rest of the edges from $v$. Call a vertex "rich" if it has more neighbors outside of its component than inside its component (i.e. $d^+(v) \ge d^-(v) + 1$) and "poor" otherwise. We say that a vertex is "noble" if $d^+(v) \ge d^-(v) + 2$. Take the partition $G = A\cup B$ with the most number rich vertices among the maximal number of crossing edges. Rich vertices $v$ satisfy $d^+(v) \ge \frac 3 2 d^-(v)$ from $d(v) := d^+(v) + d^-(v) \le 5$. Let $R_A,R_B$ denote the set of rich vertices in $A,B$, respectively and $P_A, P_B$ the sets of poor vertices in $A,B$ respectively. Claim 1: If a vertex $w$ is poor then $d^+(w) = d^-(w)$. Proof: Suppose otherwise. Moving $w$ to the other component creates a partition with more crossing edges, contradiction. Claim 2: For any $v,w$ joined by a crossing edge, if $w$ is poor then $v$ is noble. Proof: Suppose otherwise, say $w \in A$ is poor and $v\in B$ is not noble. Move $w$ into $B$, $d^+(w)$ increases by $1$ and $d^-(w)$ decreases by $1$, while the number of crossing edges stays fixed. So now $d^+(w) > d^-(w)$ and we can move $v$ to $A$ and increase the number of crossing edges. For the remainder, denote by $E_{XY}$ the number of crossing edges between components $X,Y$, $E_X$ the number of edges within set $X$. Claim 3: $E_{R_AR_B} + 2E_{P_AR_B} \ge \frac 3 2 (2E_{R_B} + 2E_{P_A} +E_{R_BP_B}+ E_{P_AR_A})$. First note that if we prove Claim 3 then add the symmetric inequality (with $A,B$ swapped) then we get the desired result of the problem (note that $E_{P_AP_B} = 0$). Proof of Claim 3: For the inequality it is equivalent to show that $$\sum_{r\in R_B} d^+(r) + \sum_{p\in P_A} d^+(p) \ge \frac 3 2 \left(\sum_{p\in P_A} d^-(p) + \sum_{r\in R_B} d^-(r)\right).$$Let $N$ be the nobility class within the rich vertices and denote by $M = R_B \setminus N$ the merchant class. Since the merchant class does not interact with the peasantry $P_A$ and for all $m\in M$ we have $d^+(m) = d^-(m) + 1 \ge \frac 3 2 d^-(m)$, it suffices to show that $$\sum_{r\in N} d^+(r) + \sum_{p\in P_A} d^+(p) \ge \frac 3 2 \left(\sum_{p\in P_A} d^-(p) + \sum_{r\in N} d^-(r)\right). \qquad\qquad (*)$$ Note that $(1)$ $d^+(p) = d^-(p)$ for any peasant $p$ $(2)$ $\sum_{r} d^+(r) \ge \sum d^+(p) = \sum d^-(p)$ because all edges going out of $P_A$ end in $R_B$ $(3)$ $d^+(r) - d^-(r) \ge 2$ for any noble $r$ and $d^+(r) + d^-(r) \le 5 \implies d^-(r) \le 1$, which when combined with $r$ noble, implies $3d^-(r) \le d^+(r)$. Now we may rewrite $(*)$ using $(1)$ as $$2\sum d^+(r) \ge \sum d^-(p) + 3\sum d^-(r).$$Now using $(2) + \sum_r (3)$ gives the desired result.

hyperbolictangent wrote: First, remark that a graph with maximum degree $\Delta$ can be properly (vertex)-colored using no more than $\Delta + 1$ colors. Indeed, simply order the vertices arbitrarily and assign to each vertex a color different from those assigned to any of its neighbors that have already been encountered. Since the latter constitute a set of size at most $\Delta$, one of our $\Delta + 1$ colors will always do the trick. Thus our resulting graph $G$ can be properly $6$-colored. Now, choose $3$ colors from the $6$ uniformly at random (so that all triples are equally likely) and collapse them into a single color - say red. Collapse the remaining $3$ colors into a single, different color - call this one blue. Then our original $6$-coloring induces a (likely improper) red-blue coloring of the vertices of $G$. The probability that any particular edge of $G$ is monochromatic with respect to this coloring is \[\frac{2 \cdot 4}{\binom{6}{3}} = 2/5\]so that the expected number of monochromatic edges under this coloring is most $2|E|/5$. Then there must exist some particular choice of partition (ergo, 2-coloring) for which no more than $2/5$ of the edges of $G$ are monochromatic - that is to say, at least $3/5$ of the edges of $G$ have endpoints of different colors. I don't understand. What is wrong with this solution? @dgrozev ?

Nothing wrong. Nice solution. Maybe I didn't get it properly, don't know. Sorry!