Find greatest possible length k of a circuit in such a graph
Source: Vietnam TST 1995, Problem 4
July 27, 2008
combinatorics unsolvedcombinatorics
Problem Statement
A graph has vertices and \frac {1}{2}\left(n^2 \minus{} 3n \plus{} 4\right) edges. There is an edge such that, after removing it, the graph becomes unconnected. Find the greatest possible length of a circuit in such a graph.