VN-TST 1995 Problem 4

A graph has $n$ vertices and $\frac {1}{2}\left(n^2 - 3n + 4\right)$ edges. There is an edge such that, after removing it, the graph becomes unconnected. Find the greatest possible length $k$ of a circuit in such a graph.