greatitself.
Continue
foundation22 min studyLesson 109 in Mathematics

Extremal and minimal counterexamples

Choose a measurable smallest failure or largest admissible object and extract information from the impossibility of improving it.

Before you begin
On this page

The question for today

What you’ll understand

  • State the domain and measure that justify an extremal choice.
  • Use minimality to obtain a valid smaller-case hypothesis.
  • Distinguish a local improvement argument from a claim of global optimality.

An arbitrary counterexample may be too complicated to understand. A smallest counterexample comes with extra information: every admissible smaller object works. An extremal object likewise comes with the promise that no allowed improvement exists. These promises can drive a proof, provided the object really exists and “smaller” or “better” has a precise meaning. The method rewards a careful choice of measure rather than a dramatic final contradiction.

Make the extremal choice legitimate

For a nonempty finite set of real scores, a maximum and minimum exist because finitely many comparisons suffice. For an infinite set, neither is automatic. The real interval from zero to one with endpoints excluded is bounded, but it contains no largest or smallest member. Well-ordering supports a minimum for nonempty sets of natural-number sizes, even when infinitely many objects have those sizes. Specify the domain, the score, and the existence reason before selecting an extremal object.

A minimal counterexample is minimal according to the chosen measure, not necessarily unique. If several failing objects have the same least size, choose any one; no uniqueness claim is required unless a later argument uses it. Sometimes size alone is too coarse, and a secondary measure helps. Lexicographic pairs of nonnegative integers are well ordered, but the proof must show the chosen transformation actually decreases the first changing coordinate. Merely making a picture look simpler is not an order argument.

B⊆N,B≠∅⟹∃b∈B ∀c∈B: b≤cB\subseteq\mathbb N,\quad B\ne\varnothing\quad\Longrightarrow\quad \exists b\in B\ \forall c\in B:\ b\le c
A nonempty set of natural-number counterexample sizes has a least size. This assertion does not extend to arbitrary subsets of real scores.↔ Scroll wide equations horizontally.

Minimality gives information about every smaller case

Suppose a theorem about finite objects fails and choose a failing object with the fewest components. Removing a component may produce a smaller valid object, to which the theorem applies. The challenge is reconstructing the original object while preserving the desired property. If reconstruction succeeds, the chosen object was not a failure after all. If removal leaves the class of admissible objects, however, the theorem cannot be invoked. Admissibility is as essential as the strict decrease in size.

As an arithmetic example, suppose an integer at least two lacking a prime-product representation is chosen least. It cannot be prime, because a single prime is already a representation. Therefore it factors into smaller integers greater than one. Those smaller factors are not counterexamples by minimality, so each has a prime-product representation, and multiplying them contradicts the chosen failure. This proof is strong induction in another form; it establishes existence, while uniqueness remains a separate mathematical task.

Extremal choices can force local structure

Consider a nonempty finite simple undirected graph whose edges have no direction and whose vertices have no loops. Choose a simple path with the largest number of vertices; such a path exists because the graph is finite and a one-vertex path is available in any nonempty graph. Every neighbor of either endpoint must already occur on the path. Otherwise appending that outside neighbor would give a longer simple path, contradicting maximal length. The extremal choice converts a global optimization into a local endpoint restriction.

This argument distinguishes maximum from merely maximal. A maximum path has greatest possible length among all simple paths; a maximal path merely cannot be extended at its ends in the chosen way. The endpoint restriction also follows for an unextendable path, but other arguments may need the stronger maximum property. More generally, a local improvement rule can stop far from a globally best object. A proof must explain why the particular absence of improvement forces the exact claimed structure.

P=(v0,…,vk) longest simple path⟹N(v0)∪N(vk)⊆{v0,…,vk}P=(v_0,\ldots,v_k)\text{ longest simple path}\quad\Longrightarrow\quad N(v_0)\cup N(v_k)\subseteq\{v_0,\ldots,v_k\}
In a finite simple graph, an endpoint neighbor outside the chosen path would extend it. N(v) denotes the set of vertices adjacent to v.↔ Scroll wide equations horizontally.

Work it through

A least positive remainder forces divisibility

For a fixed positive integer a, consider the positive integers of the form ax + by with integer x,y, where b is another fixed positive integer. Show their least member d divides a.

  1. The set is nonempty because a = a·1 + b·0 belongs to it. By well-ordering choose its least positive member d = au + bv for integers u and v.

  2. Use integer division to write a = qd + r with 0 ≤ r < d. Then r = a − q(au + bv) = a(1 − qu) + b(−qv), so r has the same required integer-linear-combination form.

  3. If r were positive, it would be a smaller positive member of the set, contradicting minimality of d. Thus r = 0, so a = qd and d divides a.

The result

The minimum positive integer combination divides a. The same remainder argument, with b in place of a, also shows it divides b.

The living notebook

Explore the model

Interactive lab

Interactive lab · optimization

Local motion and a global claim

Choose initial x₀ and compare descent step sizes below and above 2 on f(x)=x2/2f(x)=x^2/2. Predict whether each step improves the objective. In this strictly specified quadratic, algebra connects the update to the global minimizer zero. The lab is not evidence that every locally improving method solves an arbitrary nonconvex optimization problem.

Local motion and a global claimGradient descent on f(x) = x²/2: xₙ = (1 − η)ⁿx₀. Playback advances two discrete iterations per second. Values outside |x| ≤ 4 are explicitly reported. Current readings: Position x0: 2; Objective x²/2: 2; Iteration behavior: Stable step. All parameters are adjustable with the labeled controls below.−4−202402.174.356.528.7Parameter xf(x) = x²/2n = 0
ObjectiveDiscrete iterate
Position x0
2
Objective x²/2
2
Iteration behavior
Stable step
n = 0 · t = 0 s

Gradient descent on f(x) = x²/2: xₙ = (1 − η)ⁿx₀. Playback advances two discrete iterations per second. Values outside |x| ≤ 4 are explicitly reported. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forState why a local improvement or its absence has the global consequence your proof needs.

Pause & reason

Check your understanding

What must be checked before applying a theorem to a smaller object in a minimal-counterexample proof?

Your turn

Try it yourself

Prove that a finite simple graph in which every vertex has degree at least two contains a cycle. Assume the graph has at least one vertex.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Choose a longest simple path and inspect an endpoint’s neighbors.

Compare with the solution

A longest simple path exists by finiteness. Every neighbor of an endpoint is on that path, since an outside neighbor would extend it. The endpoint has at least two distinct neighbors. One may be its immediate predecessor on the path, but another must occur earlier. Follow the path from that earlier neighbor to the endpoint, then take their connecting edge back. Its vertices are distinct until the return, so it is a cycle of length at least three.

Keep the idea

Take it with you

  • An extremal choice needs an explicit existence justification.
  • Smaller objects must remain admissible for the theorem being used.
  • Local improvement arguments need a precise bridge to any global conclusion.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.