A remark on the number of edge colorings of graphs

Fix a 2-coloring H k + 1 of the edges of a complete graph K k + 1 . Let C ( n , H k + 1 ) denote the maximum possible number of distinct edge-colorings of a simple graph on n vertices with two colors, which contain no copy of K k + 1 colored exactly as H k + 1 . It is shown that for every fixed k and all n > n 0 ( k ) , if in the colored graph H k + 1 both colors were used, then C ( n , H k + 1 ) = 2 t k ( n ) , where t k ( n ) is the maximum possible number of edges of a graph on n vertices containing no K k + 1 . The proofs are based on Szemerédi’s Regularity Lemma together with the Simonovits Stability Theorem, and provide one of the growing number of examples of a precise result proved by applying the Regularity Lemma.