Extremal Principle

In a finite simple graph, every vertex has degree at least 2. Prove that the graph contains a cycle.

Solution

Choose a longest simple path

Since this path is longest, every neighbor of v_k must already belong to the path. Otherwise, we could extend the path.

$Since v_k has degree at least 2, it has a neighbor v_i with i ≤ k − 2, in addition to v_{k−1}.$

Therefore,

forms a cycle.

Extremal choice: The longest simple path.

There are n red points and n blue points in the plane, with no three points collinear. Prove that we can connect each red point to exactly one blue point so that no two connecting segments intersect.

Solution

Among all possible matchings, choose one minimizing the sum of the lengths of its segments.

Suppose two segments R₁B₁ and R₂B₂ intersect at X.

By the triangle inequality,

Adding gives

Replacing the crossing segments with R₁B₂ and R₂B₁ produces a matching with smaller total length, a contradiction. ✗

Therefore, the minimum-length matching has no crossings. ✓

Extremal choice: The matching with minimum total length.

Several real numbers are arranged around a circle. Each number is equal to the average of its two neighboring numbers. Prove that all the numbers are equal.

Solution

Let M be the largest number.

Suppose its neighbors are a and b. Then

But

Therefore,

Applying the same argument to neighboring positions, we conclude that every number equals M.

Extremal choice: The largest number.