Skip to content / Đến nội dung
ThichHocToan.com

IMO 2004 — Complete Shortlist Question 10

IMO Shortlist · IMO 2004 — Complete Shortlist

Question 10

The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer $ n \geq 4 $, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on n vertices (where each pair of vertices are joined by an edge).