Can someone explain the basic idea behind proof by extremality in simple language?
Like in proof by contradiction, for $P \rightarrow Q$, we assume $P$ and not $Q$ and show they cannot happen simultaneously.
Also, an example of a proof by extremality.
Thank you!
On
There is already one answer, but I wanted to go into more detail. I haven't quite heard it called proof by extremality, but assuming I am think of the same thing, here is what it is:
This is actually a sub case of a proof by contradiction(it may be able to be done with a direct proof, but I can't think of an example). It is a common technique in combinatorics because of the finite, discrete nature of many combinatorics problems.
How it works is if we want to prove some proposition true for a collection of objects, then we can assume to the contrary that is is false for at least one object. Then(if our collection of objects has certain properties) we can find say if it's false for one object, we can find a "smallest" or "largest" object for which it is false for. Let's say we find a smallest object. Then, if we can somehow prove that there is an even smaller object that it is false for, we contradict the assumption that we had a smallest one.(note I use the word "a" here because there can be multiple smallest objects.)
This technique is used a lot in graph theory because if a proposition doesn't hold for all graphs, then there is some number $n$ such that there is a graph of order $n$ that it fails for but there are no graphs of order $n-1$ for which it fails for. We can also do this for size or for girth or for plenty of other properties. This works because if there is a counter example of order say $n$ then there are only finitely many graphs of order less than $n$ so by finiteness there must be a "smallest" one.
An easy example that shows it can be used outside of graph theory(note, I am not suggesting that this is the best way to prove this, just that it is a valid way.)
Theorem: $\sin\pi x=0$ for all $x\in\mathbb{Z}$
Proof: first, we can directly verify that this is not true for $0, 1$ and $-1$. Now assume to the contrary that there exists some $x\in\mathbb{Z}$ such that $\sin\pi x\neq 0$. Then we can find an $n$ such that $\sin\pi n\neq 0$ but for all $k\in\mathbb{Z}$ with $|k|<|n|$, $\sin\pi k=0$ since there are only finitely many integers with absolute value less than x. Due to our direct calculations, we know $|n|\geq 2$. Observe that $$ \sin\pi (n\pm 2)=\sin(\pi n\pm2\pi)=\sin\pi n\neq 0$$ since the period of $\sin$ is $2\pi$. This contradicts the minimality of n though since one of $n\pm 2$ has absolute value less than $n$. Thus, $\sin\pi x=0$ for all $x\in\mathbb{Z}$. QED
Hope this helps.
Just asked my graph theory Professor:
A proof by extremality is one which looks solely at the extreme cases in order to show something is true or false.
A graph theory example would be proving that a uv-walk (an ordered list of vertices from u to v) contains a uv-path (an ordered list of vertices which can't repeat from u to v).
Something like:
For some uv-walk w, any path which repeats a vertex must loop, causing extra vertices to be reached. Therefore a walk which removes all repeated portions would be shorter. Therefore the shortest uv-walk contained in w is also a uv-path. Therefore all uv-walks contain uv-paths.
That help?