Here $G_{n}$ denotes a simple undirected graph with $n$ vertices, $K_{n}$ denotes the complete graph with $n$ vertices, $K_{n,m}$ the complete bipartite graph whose components have $m$ and $n$ vertices, and $C_{n}$ a circuit with $n$ vertices. The number of edges in the graph $G_{n}$ is denoted $e(G_{n})$. The edges of $K_{n}(n \geq 3)$ are colored with $n$ colors, and every color is used. Show that there is a triangle whose sides have different colors.
Problem
Source: 12-th Hungary-Israel Mathematical Competition 2001
Tags: induction, graph theory, combinatorics proposed, combinatorics
azi
16.09.2008 03:23
By induction on $ n$. For $ n = 3$ the statement clearly holds so we assume it holds for $ k \geq n$ and consider the graph $ K_{n+1}$. Let $ v$ be an arbitrary vertex of $ K_{n+1}$ and define $ K : = K_{n+1} - v$. If the edges of $ K$ are colored with $ n$ different colors we are done. So, suppose the edges of $ K$ are colored with $ n + 1$ colors. Recolor the edges of color $ n + 1$ with a different color, say n. By the induction hypothesis $ K$ now contains the specified triangle $ T$. It is easy to verify that $ T$ satisfies the required conditions even in $ K_{n+1}$.
Erken
18.09.2008 16:59
Hmm...solution above seems wrong to me,what makes you think that you can recolor vertices? I had essentially the same problem at my IMO Preparation course,and if I am not mistaken five of our 6 members managed to solve it,the one who didn't(not me),was pretty surprised when some of us showed the proof...it is pretty simple,though I must admit that it took one or two hours to find a solution. I've got to thing some to recall the details but the first step is clear to everyone,I guess.
pbornsztein
23.09.2008 00:04
Let's choose one edge for each color. Thus, you get a graph with $ n$ vertices and $ n$ edges. Therefore, this graph has a cycle. It follows that the initial graph contains rainbow cycles (a rainbow cycle is a cycle with no two edges with the same color). Now, let's consider a rainbow cycle with minimal length, say $ L$. We want to prove that $ L=3$. Assume, for a contradiction, that $ L \geq 4$ and let $ A_1,A_2,A_3,A_4$ be any four consecutive vertices on this minimal rainbow cycle. The edge $ A_1A_3$ divides the cycle into two other cycles with lengths less than $ L$ and since the color of the edge $ A_1A_3$ appears at most once in the minimal rainbow cycle, it does not appear in some of these two parts. Thus, we have found a rainbow cycle with length les than $ L$, contradicting the minimality of $ L$, and we are done. Pierre.
atreides
23.09.2008 05:13
I don't know if this is what Azi meant to say. Clearly the statement is true for n = 3. We now use induction: Suppose it's true for n < k, we show it's true for k. Choose a vertex A in k and cosider the remaining k-1 complete graph. If that graph is coloured by k-1 or more colours, then we have our triangle (by induction hypothesis). Otherwise there must be less than k - 1 colours in the k-1 graph, so there are at least two colours (i.e. red and blue) not in the k-1 graph but in the k graph (i.e. they are attached to A). Thus AB is red and AC is blue for some B and C. But BC cannot be red or blue since the edge is in the k-1 graph. Thus ABC is a different coloured triangle. So my PMI, it is true for all n >= 3.