Multiplicities of subgraphs (Q1912755)

To each graph \(H\) on \(n\) vertices we may associate a 2-coloring of the edges of the complete graph \(K_n\) by taking the edges of \(H\) to be one color class and the edges of its complement \(\overline H\) to be the other. Given a coloring \(H\), we define \(c(G; H)\) to be the proportion of the copies of \(G\) in \(K_n\) which are monochromatic and \(c(G; n)\) to be the minimum of \(c(G; H)\) over all colorings \(H\) of \(K_n\). It is not difficult to show that \(c(G; n)\) has a limit as \(n\to \infty\), which we denote by \(c(G)\). The average value of \(c(G; H)\) over all graphs \(H\) is \(2^{1- e(G)}\); hence, \(c(G)\leq 2^{1- e(G)}\). A graph \(G\) is said to be common if the equality holds and uncommon if the strict inequality holds. The authors prove several interesting results about these concepts including Theorem 8: The even wheel \(W_{2k}\) is common for \(k\geq 2\). And their main result is Theorem 12: Every graph containing \(K_4\) is uncommon.