We have a complete graph with $n$ vertices. We have to color the vertices and the edges in a way such that: no two edges pointing to the same vertice are of the same color; a vertice and an edge pointing him are coloured in a different way. What is the minimum number of colors we need?
Problem
Source: Italian TST , day 2, n°1
Tags: inequalities, graph theory, combinatorics proposed, combinatorics
02.06.2007 22:19
assume the the minimum number of colors needed is $s$... take an arbitary vertex,this vertex with its edges are $n$ objects which must be colored in different colors,so $n\leq s$... the only thing that remains is to give an example using $n$ colors: first of all name the colors $1,...,n$,then color the vertices from $1$ to $n$,now for every edge $e$ between vertices $u,v$,color $e$ with the color $u+v (\bmod n)$... this coloring has the properties of the problem,its easy to prove,assume that edges $e,e'$ between vertices $a,b$ and $a,c$ had the same color then we would have $a+b \equiv a+c (\bmod n)$ so we get that $b \equiv c (\bmod n)$ so we get that $a=c$ which is a contradiction,so this coloring has the property of the problem...
04.06.2007 23:56
The edge between 1 and n has colour 1+n=1??? (it seems a contradiction)
30.07.2007 10:33
The mistake can be corrected if you first just number the vertices from $ 1$ to $ n$ (you don't actually color them), after you color the edges like Ghalebi said, these will be colored correctly, and only when we are done with this we color the vertices(to each vertex there will be $ n-1$ edges pointing to it, so we can always choose the $ n$th color).
06.08.2019 14:26
The original problem was stated in form of computers and cables Simo_the_Wolf wrote: We have a complete graph with $n$ vertices. We have to color the vertices and the edges in a way such that: no two edges pointing to the same vertex are of the same color; a vertex and an edge pointing him are colored in a different way. What is the minimum number of colors we need? Answer: We show that a desired coloring can be achieved with the use of $n$ colors. Solution. Firstly as $n$ vertices are to be colored differently, the number of colors required is obviously $\ge n$. Next color the vertices and the edges as follows: Label the vertices of $K_n$ as $1,2, \dots , n$ and color the edge joining $\{i,k\}$ with the color $C_{\overline{i+j}}$ where $\overline{i+j} = i+j \pmod n , 0 \le i \neq j < n$. Once done with this, observe that each vertex has its degree equal to $n-1$ which means that it has been connected with $n-1$ edges, all colored differently. So we can always choose the $n^{\text{th}}$ color amongst $C_1 , C_2 , \dots , C_n$. To show that this coloring indeed satisfies the problem condition ,if two edges have the same color $\iff i + j \equiv i+k \pmod n \iff j=k ,$ contradiction. Hence $n$ is indeed the minimum.
05.02.2022 13:53
The minimum is $n$. Assume that the number of colors needed is less than $n$, then by the condtions, we must then have a vertex whose one output edge is the same color as he is. Thus we know that the minimum is $\geq n$. Algorithm: Color the n vertices with different colors, then from a vertex send out a ray the first pair it hits, colour their edge with the vertex color, let the ray run until it hits the rest of the vertices. By this way we assure that every vertex, follows the conditions.
22.02.2022 23:05
Luis is finally doing Graph Theory (I assume $n$ is odd as when i've set $n$ to be some even number i needed more than $n$ colors) Assume that the number of colors u need it less than $n$, then by pigeonhole we have that 2 vertices will have the same color and that would be a contradiction. Hence the number we want is greater or equal than $n$. First we let $n=2k+1$ and now to make a construction with $2k+1$ colors we do this, pick the vertex $v_i$ which has color $c_i$ where $1 \le i \le 2k+1$, now from $v_i$ paint all the edges that are oposite to $v_i$ of the color $c_i$. Now it remains to verify that this process paintd all the edges of the graph, which is true since we do this process $2k+1$ times and the number of lines oposite to $v_i$ are $k$, and since $\binom{2k+1}{2}=k(2k+1)$ we are done
22.02.2022 23:08
Let the vertices be labeled $1$, $2$, $\ldots$, $n$, and the colors of the vertices are labeled the same way. Then, let the edges joining $2$ and $n$, $3$ and $n-1$, etc. have color $1$, and color the other edges similarly. Then, each edge is colored and satisfies all of the conditions. Therefore, at least $\boxed n$ colors are required.
05.08.2022 03:06