Maximum Number of \(3\)-Paths in a Graph

Abstract

In this paper, we show that a graph \(G\) with \(e \geq 6\) edges contains at most \(\frac{h(h-1)(h-2)(h-3)}{2}\) paths of length three, where \(h \geq 0\) satisfies \(\frac{h(h-1)}{2} = e\). It follows immediately that \(G\) contains at most \(\frac{h(h-1)(h-2)(h-3)}{8}\) cycles of length four. For \(e > 6\), the bounds will be attained if and only if \(h\) is an integer and \(G\) is the union of \(K_h\) and isolated vertices. The bounds improve those found recently by Bollobás and Sarkar.