# Long Cycles in Euclidean 2-Factors

(suggested by William Cook)

Given a set *S* of points in the plane, a *minimum 2-factor* is a collection of circuits such that every point in *S* is a member of exactly one circuit in the collection and the sum of the Euclidean lengths of the edges in the circuits is as small as possible. An example of a minimum 2-factor is shown in the figure below, where the 10,000 points were selected uniformly at random in the unit square.

Notice that one of the circuits, colored red, contains a large fraction of the point set (2,264 of the 10,000 points). The problem is to show that this happens with high probability. That is, given a collection of *n* points in the unit square, selected uniformly at random, and a minimum 2-factor *F*, does *F* have with high probability a circuit of length at least *cn* for some positive constant *c*?