# Minimal counterexample

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Minimal_counterexample
> Markdown URL: https://mediated.wiki/source/Minimal_counterexample.md
> Source: https://en.wikipedia.org/wiki/Minimal_counterexample
> Source revision: 1352723842
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Smallest example which falsifies a claim

"Minimal criminal" redirects here. For the musical project, see [Minimal Criminal (project)](/source/Minimal_Criminal_(project)).

In [mathematics](/source/Mathematics), a **minimal counterexample** is the smallest example which falsifies a claim. It is also sometimes called a **minimal criminal**,[1] **smallest criminal**,[2] or **least criminal**,[3][4] especially (but not exclusively) in the context of the [four-color theorem](/source/Four_color_theorem).[5][6][7][8][9] A **proof by minimal counterexample** (or by *minimal/smallest/least criminal*) is a method of [proof](/source/Mathematical_proof) which combines the use of a minimal counterexample with the methods of [proof by induction](/source/Proof_By_Induction) and [proof by contradiction](/source/Proof_by_contradiction).[10][11] More specifically, in trying to prove a proposition *P*, one first assumes by contradiction that it is false, and that therefore there must be at least one [counterexample](/source/Counterexample). With respect to some idea of size (which may need to be chosen carefully), one then concludes that there is such a counterexample *C* that is *minimal*. In regard to the argument, *C* is generally something quite hypothetical (since the truth of *P* excludes the possibility of *C*), but it may be possible to argue that if *C* existed, then it would have some definite properties which, after applying some reasoning similar to that in an inductive proof, would lead to a contradiction, thereby showing that the proposition *P* is indeed true.[12]

If the form of the contradiction is that we can derive a further counterexample *D*, that is smaller than *C* in the sense of the working hypothesis of minimality, then this technique is traditionally called [proof by infinite descent](/source/Proof_by_infinite_descent). In which case, there may be multiple and more complex ways to structure the argument of the proof.

The assumption that if there is a counterexample, there is a minimal counterexample, is based on a [well-ordering](/source/Well-ordering) of some kind. The usual ordering on the [natural numbers](/source/Natural_number) is clearly possible, by the most usual formulation of [mathematical induction](/source/Mathematical_induction); but the scope of the method can include [well-ordered induction](/source/Well-ordered_induction) of any kind.

## Examples

The minimal counterexample method has been much used in the [classification of finite simple groups](/source/Classification_of_finite_simple_groups). The [Feit–Thompson theorem](/source/Feit%E2%80%93Thompson_theorem), that finite simple groups that are not cyclic groups have even order, was proved based on the hypothesis of some, and therefore some minimal, simple group *G* of odd order. Every proper subgroup of *G* can be assumed a solvable group, meaning that much theory of such subgroups could be applied.[13]

[Euclid's proof of the fundamental theorem of arithmetic](/source/Fundamental_theorem_of_arithmetic#Proof) is a simple proof which uses a minimal counterexample.[14][15]

A minimal counterexample has often been used in proofs of the [four-color theorem](/source/Four_color_theorem), where it is usually called a *minimal criminal*.[5][6][7][8][9]

## References

1. **[^](#cite_ref-1)** belcastro, sarah-marie (2012-06-21). [*Discrete Mathematics with Ducks*](https://www.google.com.br/books/edition/Discrete_Mathematics_with_Ducks/UYtlK8waqasC). CRC Press. p. 107. [ISBN](/source/ISBN_(identifier)) [978-1-4665-0499-8](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4665-0499-8).

1. **[^](#cite_ref-2)** Hofmann, Karl H.; Morris, Sidney A. (2020-06-08). [*The Structure of Compact Groups: A Primer for the Student – A Handbook for the Expert*](https://www.google.com.br/books/edition/The_Structure_of_Compact_Groups/tlw8EAAAQBAJ). Walter de Gruyter GmbH & Co KG. p. 250. [ISBN](/source/ISBN_(identifier)) [978-3-11-069601-1](https://en.wikipedia.org/wiki/Special:BookSources/978-3-11-069601-1).

1. **[^](#cite_ref-3)** [*Mathematics Magazine*](https://www.google.com.br/books/edition/Mathematics_Magazine/CNE3AAAAIAAJ). Vol. 54. Mathematical Association of America. 1981. p. 24.

1. **[^](#cite_ref-4)** Cameron, Peter Jephson (1998). [*Introduction to Algebra*](https://www.google.com.br/books/edition/Introduction_to_Algebra/syYYl-NVM5IC). Oxford University Press. p. 17. [ISBN](/source/ISBN_(identifier)) [978-0-19-850195-4](https://en.wikipedia.org/wiki/Special:BookSources/978-0-19-850195-4).

1. ^ [***a***](#cite_ref-:0_5-0) [***b***](#cite_ref-:0_5-1) [Wilson, Robin](/source/Robin_Wilson_(mathematician)) (2021-10-12). [*Four Colors Suffice: How the Map Problem Was Solved - Revised Color Edition*](https://www.google.com.br/books/edition/Four_Colors_Suffice/1Q48EAAAQBAJ). Princeton University Press. pp. 51–52. [ISBN](/source/ISBN_(identifier)) [978-0-691-23756-5](https://en.wikipedia.org/wiki/Special:BookSources/978-0-691-23756-5).

1. ^ [***a***](#cite_ref-:1_6-0) [***b***](#cite_ref-:1_6-1) Fritsch, Rudolf; Fritsch, Gerda (2012-12-06). [*The Four-Color Theorem: History, Topological Foundations, and Idea of Proof*](https://www.google.com.br/books/edition/The_Four_Color_Theorem/me3jBwAAQBAJ). Springer Science & Business Media. pp. 85–87. [ISBN](/source/ISBN_(identifier)) [978-1-4612-1720-6](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4612-1720-6).

1. ^ [***a***](#cite_ref-:2_7-0) [***b***](#cite_ref-:2_7-1) Wilson, Robert (2002). [*Graphs, Colourings and the Four-colour Theorem*](https://www.google.com.br/books/edition/Graphs_Colourings_and_the_Four_colour_Th/9FPCJUCc7QEC). Oxford University Press. p. 36. [ISBN](/source/ISBN_(identifier)) [978-0-19-851061-1](https://en.wikipedia.org/wiki/Special:BookSources/978-0-19-851061-1).

1. ^ [***a***](#cite_ref-:3_8-0) [***b***](#cite_ref-:3_8-1) Xu, Jin (2025-05-23). [*Maximal Planar Graph Theory and the Four-Color Conjecture*](https://www.google.com.br/books/edition/Maximal_Planar_Graph_Theory_and_the_Four/RalfEQAAQBAJ). Springer Nature. p. 95. [ISBN](/source/ISBN_(identifier)) [978-981-96-4745-3](https://en.wikipedia.org/wiki/Special:BookSources/978-981-96-4745-3).

1. ^ [***a***](#cite_ref-:4_9-0) [***b***](#cite_ref-:4_9-1) [Richard Courant](/source/Richard_Courant); [Herbert Robbins](/source/Herbert_Robbins) (1996). *What is Mathematics?* (2nd ed.). Oxford: Oxford University Press. [ISBN](/source/ISBN_(identifier)) [9780195105193](https://en.wikipedia.org/wiki/Special:BookSources/9780195105193). Here: p.495: *"Since there is no point in making bad maps bigger, we go the opposite way and look at the smallest bad maps, colloquially known as minimal criminals."*

1. **[^](#cite_ref-10)** [Chartrand, Gary](/source/Gary_Chartrand), Albert D. Polimeni, and [Ping Zhang](/source/Ping_Zhang_(graph_theorist)). Mathematical Proofs: A Transition to Advanced Mathematics. Boston: Pearson Education, 2013. Print.

1. **[^](#cite_ref-11)** Klipper, Michael (Fall 2012). ["Proof by Minimum Counterexample"](https://web.archive.org/web/20180417050633/http://alpha.math.uga.edu/~mklipper/3200/F12/mincounter.pdf) (PDF). *alpha.math.uga.edu*. Archived from [the original](http://alpha.math.uga.edu/~mklipper/3200/F12/mincounter.pdf) (PDF) on 2018-04-17. Retrieved 2019-11-28.

1. **[^](#cite_ref-12)** Lewis, Tom (Fall 2010). ["§20 Smallest Counterexample"](http://math.furman.edu/~tlewis/math260/scheinerman/chap4/sec20.pdf) (PDF). *math.furman.edu*. Retrieved 2019-11-28.

1. **[^](#cite_ref-13)** [Feit, Walter](/source/Walter_Feit); [Thompson, John G.](/source/John_G._Thompson) (1963), ["Solvability of groups of odd order"](http://projecteuclid.org/Dienst/UI/1.0/Journal?authority=euclid.pjm&issue=1103053941), *Pacific Journal of Mathematics*, **13**: 775–1029, [doi](/source/Doi_(identifier)):[10.2140/pjm.1963.13.775](https://doi.org/10.2140%2Fpjm.1963.13.775), [ISSN](/source/ISSN_(identifier)) [0030-8730](https://search.worldcat.org/issn/0030-8730), [MR](/source/MR_(identifier)) [0166261](https://mathscinet.ams.org/mathscinet-getitem?mr=0166261)

1. **[^](#cite_ref-14)** ["The Fundamental Theorem of Arithmetic | Divisibility & Induction | Underground Mathematics"](https://undergroundmathematics.org/divisibility-and-induction/the-fundamental-theorem-of-arithmetic). *undergroundmathematics.org*. Retrieved 2019-11-28.

1. **[^](#cite_ref-15)** ["The fundamental theorem of arithmetic"](https://www.dpmms.cam.ac.uk/~wtg10/FTA.html). *www.dpmms.cam.ac.uk*. Retrieved 2019-11-28.

---
Adapted from the Wikipedia article [Minimal counterexample](https://en.wikipedia.org/wiki/Minimal_counterexample) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Minimal_counterexample?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.