3 colors for a figure by 10 nodes and 15 edges
Source: Chile Finals 2011 L2 p3
October 5, 2022
combinatoricsColoring
Problem Statement
Consider the following figure formed by nodes and edges:[asy]
unitsize(1.5 cm);pair A, B, C, D, E, F, G, H, I, J;A = dir(90);
B = dir(90 + 360/5);
C = dir(90 + 2*360/5);
D = dir(90 + 3*360/5);
E = dir(90 + 4*360/5);
F = 0.6*A;
G = 0.6*B;
H = 0.6*C;
I = 0.6*D;
J = 0.6*E;draw(A--B--C--D--E--cycle);
draw(F--H--J--G--I--cycle);
draw(A--F);
draw(B--G);
draw(C--H);
draw(D--I);
draw(E--J);dot(A);
dot(B);
dot(C);
dot(D);
dot(E);
dot(F);
dot(G);
dot(H);
dot(I);
dot(J);
[/asy]Prove that the edges of the figure cannot be colored by using different colors so that the edges that reach each node have different colors from each other.