Multiplicity of Triangles in \(2\)-Edge Coloring of a Family of Graphs

Let \(\{G(n,k)\}\) be a family of graphs where \(G(n, k)\) is the graph obtained from \(K_n\), the complete graph on \(n\) vertices, by removing any set of \(k\) parallel edges. In this paper, the lower bound for the multiplicity of triangles in any \(2\)-edge coloring of the family of graphs \(\{G(n, k)\}\) is calculated and it is proved that this lower bound is sharp when \(n \geq 2k + 4\) by explicit coloring schemes in a recursive manner. For the cases \(n = 2k + 1, 2k + 2\), and \(2k + 3\), this lower bound is not sharp and the exact bound in these cases are also independently calculated by explicit constructions.