The problem:
The vertices of a convex polygon of 2007 sides are numbered from 1 to
2007. Each side and diagonal are colored either in red or blue. Prove that, for any permutation of the vertices, it is always possible to
find two integers $m, n$ such that the segment connecting them has the
same color as before the permutation.
So, what I understand from the wording of the problem is that you have a polygon with sides and diagonals painted in a certain way and its vertices numbered from 1 to 2007. A permutation of the vertices would be something like changing the numbers on the vertices and leaving the overall color-setting unchanged. The following image shows and example for a pentagon.
My attempt
If my interpretation of the problem is correct, then my approach consists in trying to use the pigeonhole principle somehow. First, I thought I could think of two sets, let's say $R$ and $B$ such that they are composed by all the $(a,b)$, with $a \ne b$ between 1 to 2007 that are connected by a red or blue segment, respectively. Now, the amount of diagonals and segments is $(1002)(2007)+2007$, an odd amount. That means $|R|+|B|$ must be an odd number, which implies that one of them is greater than the other, or in other words, the mimimal difference between them is 1.
Suppose, for example, that $|R|=|B|+1$ then at least one of the pairs of numbers in the $R$ set will have to remain there, meaning the color of the segment joining them will be the same as before the permutation.
Concerns
At first I thought this could be right, but when checking for a particular case (a square), I realized one cannot simply put any arbitrary pair of numbers in whatever set, because depending on the initial configuration, there seems to be a defined limit for the types of pairs (diagonals or segments) that can be contained in sets $R$ and $B$.In other words, for a given permutation it is possible to define sets $R$ and $B$, but the converse is not true (any configuration of sets $R$ and $B$ does not necessarily results in a valid permutation of the polygon).
I would like to see some other approaches.
Best Answer
Previous nonsense completely replaced.
The graph has $\binom{2007}2=2013021$ edges. Since this is an odd number, there cannot be equal numbers of red and blue edges. Without loss of generality assume that there are more red edges than blue. Any permutation of the vertices induces a permutation of the edges, and it is clearly impossible for a permutation of the edges to send every red edge to a blue edge. Thus, some red edge must be sent to a red edge.