Connected graphs without long paths (Q941391): Difference between revisions

The authors prove the following result: Let \(G\) be a connected graph on \(n\) vertices containing no path on \(k+1\) vertices, \(n>k\geq3\). Then \(|E(G)|\) is bounded above by the maximum of \({{k-1}\choose{2}}+(n-k+1)\) and \({{\lceil(k+1)/2\rceil}\choose{2}}+\lfloor(k-1)/2\rfloor(n-\lceil(k+1)/2\rceil)\). If equality occurs then \(G\) is either \(G_{n,k,1}\) or \(G_{n,k,\lfloor(k-1)/2\rfloor}\).