Two path extremal graphs and an application to a Ramsey-type problem (Q1297399)

In any undirected simple graph \(G\), \(p_2(G)\) denotes the number of paths of length 2. \(G\) is a \((v,e)\)-graph if it has precisely \(v\) vertices and \(e\) edges; \(g(v,e)=\max\{p_2(G):G\) is a \((v,e)\)-graph\(\}\); those graphs for which the maximum is attained are called \((v,e)\)-extremal or 2-path extremal. From the author's introduction and his abstract: ``In this paper we completely classify all graphs attaining these extrema. As an application we show that, if \(H\) is a connected graph with 3 edges, the number of occurrences of \(H\) as a subgraph in \(G\) or \(G^c\) is maximized (over the class of \((v,e)\)-graphs) if and only if \(p_2(G)=g(v,e)\dots\). In [Extremal graphic sequences, Recent studies in graph theory, 159-176, Vishwa, Gulbarga, (1989)] \textit{J. W. Kennedy, P. N. Nikolakos}, and \textit{L. W. Quintas} examined degree sequences of graphs in order to maximize and minimize \(p_2(G)\) over various families of graphs \(\dots\). For some pairs \(v\) and \(e\) they constructed a \((v,e)\)-graph \(G\) such that \(p_2(G)=g(v,e)\). However, their construction does not always yield a \((v,e)\)-extremal graph, as they claimed, so their computation of \(g(v,e)\) is incorrect \(\dots\). In [The degree variance: An index of graph heterogeneity, Social Networks 3, No. 3, 163-174 (1981/82)] \textit{T. A. B. Snijders} \(\dots\) computes \(g(v,e)\) by describing two classes of \((v,e)\)-graphs and showing that one of them always contains an extremal graph. Prior to Snijders' work, in [Graphs with maximal number of adjacent pairs of edges, Acta Math. Acad. Sci. Hung. 32, 97-120 (1978; Zbl 0386.05036)] \textit{R. Ahlswede} and \textit{G. O. H. Katona} had found the same two classes and given some bounds for determining which of the two classes must contain an extremal graph. However, none of these authors classified all of the extremal graphs, a main new result of this paper \(\dots\). As an application we consider 2-colourings of the edges of \(K_v\), where exactly \(e\) edges are coloured with one colour, say `red'. It is shown that, for any connected graph \(H\) with 3 edges \(\dots\) the number of occurrences of \(H\) as a monochromatic subgraph of \(K_v\) is maximized if and only if the `red' subgraph of \(K_v\) is 2-path extremal''.