Two path extremal graphs and an application to a Ramsey-type problem Original Research Article

Let p2(G) denote the number of paths of length 2 in the graph G, and let g(v, e) = max{p2(G): G has v vertices and e edges}. In this paper we completely classify all 2-path extremal graphs, i.e., all (v, e)-graphs G such that p2(G) = g(v, e). As an application, we consider 2-colorings of the edges of Kv, where exactly e edges are colored with one color, say red. It is shown that for any connected graph H with 3 edges (triangle, 3-path, 3-star), the number of occurrences of H as a monochromatic subgraph of Kv is maximized if and only if the ‘red’ subgraph of Kv is 2-path extremal.