On the Number of Distinct Colors in Perfect Matchings
Source: Ukrainian Mathematical Olympiad 2023. Day 2, Problem 10.8
April 5, 2023
combinatoricsgraphsColoring
Problem Statement
Consider a complete graph on nodes, whose edges are colored in some colors. Let's call this graph -good if we can split all its nodes into pairs so that there are exactly distinct colors among the colors of edges that connect the nodes from the same pairs. Is it possible that the graph is -good and -good but not -good?Proposed by Anton Trygub