A remark on the number of edge colorings of graphs

Fix a 2-coloring Hk+1Hk+1 of the edges of a complete graph Kk+1Kk+1. Let C(n,Hk+1)C(n,Hk+1) denote the maximum possible number of distinct edge-colorings of a simple graph on nn vertices with two colors, which contain no copy of Kk+1Kk+1 colored exactly as Hk+1Hk+1. It is shown that for every fixed kk and all n>n0(k)n>n0(k), if in the colored graph Hk+1Hk+1 both colors were used, then C(n,Hk+1)=2tk(n)C(n,Hk+1)=2tk(n), where tk(n)tk(n) is the maximum possible number of edges of a graph on nn vertices containing no Kk+1Kk+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.