Edge Coloring Complete
Probability
Level
2
What is the minimal number such that there exists a proper edge coloring of the complete graph on 8 vertices with colors?
15
8
7
28
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The answer is 7. Choose a vertex and draw all 7 colored edges from it. Then, for any edge e coming out of it, consider the remaining 6 vertices and choose a matching of them. Color each edge in that matching the same color as e . In this way, ( 1 + 3 ) ⋅ 7 = 2 8 edges are colored, which is all of them.