Edges of each colour for Ramsey Graphs

Question

Consider a 2-coloring of the edges of a complete graph $K_{n}$. Assume it doesn't exhibit a monochromatic subgraph of $m$ vertices thus demonstrating that the Ramsey number $R(m,m)$ is greater than $n$. In the case that $R(m,m)$ is in fact $n+1$ (call such a colouring a "maximal" Ramsey graph) can we say that the number of edges of each colour in the graph are equal? I have in mind the graph on 5 vertices with all edges round the perimeter red and all internal edges blue, but I wonder if such a symmetry continues for $R(4,4)$ or even unknown Ramsey numbers like $R(5,5)$.

Answer 1

It continues at least for $R(4,4)$; the unique coloring of $K_{17}$ (which I found here) has $68$ red and $68$ blue edges. Past that point, we don't know enough to say for sure.

If this color parity were a known fact in general, it would imply that $K_{R(m,m)-1}$ has an even number of edges, which limits $R(m,m)$ to $1$ or $2$ modulo $4$. Such a limitation would let us reduce the range of possible values of $R(5,5)$ considerably: we currently have $43 \le R(5,5) \le 48$, but this would tell us that $45 \le R(5,5) \le 46$.

(I don't believe that smarter people than me would have missed this, so I conclude that there is no proof that color parity should hold.)

We do have strong reason to believe that the red and blue edges should be approximately balanced. (Beyond just reasons of fairness.) A theorem of Erdős and Szemerédi says that if a coloring of $K_{n}$ is unbalanced (more than a $\frac12+\epsilon$ fraction of the edges are blue, say) then the known guarantee that there's a monochromatic clique of order $\frac12\log_2 n$ can be improved to $(\frac12+\delta)\log_2 n$ for some $\delta>0$ (depending on $\epsilon$).

This doesn't mean anything for the actual Ramsey-maximal graphs, because maybe that lower bound is far from the truth (our upper bounds look more like $2\log_2 n$), but it's very suggestive.

---

It's worth noting that in other symmetric Ramsey problems, a symmetry between the colors does not always exist. For example, consider $R(P_{2k}, P_{2k})=3k-1$. An extremal construction here has $K_{2k-1,k-1}$ in red (so that we can't get a path longer than $2k-1$ because we run out of vertices on one side) and colors everything else blue (which can't get a path longer than $2k-1$ because it's stuck on one side of the red bipartite graph). This is not balanced: it is about $5/9$ blue.