Potent Potables
It's the proof technique you would use to show that a graph is not planar.
What is a proof by contradiction?
If a graph has chromatic number 5, then no matter how you draw it, there will be edges crossing.
What is True? This is the contrapositive of the 4-color theorem.
\(Q\rightarrow P\)
What is the converse?
The number of 4-letter words.
What is \(26^4\), or 456976?
1, 3, 6, 10, 15, 21, 28, ...
What are the triangular numbers?
To prove that \(n\binom{n-1}{k-1} = k\binom{n}{k}\) you could give an algebraic proof or this kind of proof.
What is a combinatorial proof?
The converse of, "If two graphs have the same degree sequence, then they are isomorphic."
What is True? (But the original statement is false.)
\(\neg Q \rightarrow \neg P\)
What is the contrapositive?
The number of 4-letter words containing no repeated letters.
What is \(P(26,4)\), or 358800?
The recursive definition of the sequence \(2, 5, 7, 12, 19, 31,\ldots\)
What is \(a_n = a_{n-1} + a_{n-2}\); \(a_0 = 2\) and \(a_1 = 5\)?
This is what you would use to prove a fact about a recurrence relation.
What is proof by mathematical induction?
\((P \rightarrow Q) \vee P\)
What is True?
\(P \wedge \neg Q\)
What is the negation?
The number of 4-letter words in which the letters are in alphabetical order.
What is \({29 \choose 4}\), or 23751?
A closed formula for \(1+3+5+7+\cdots + (2n-1)\).
What is \(n^2\)?
You would use this style of proof to establish that if \(A \subseteq B\) and \(B \subseteq C\), then \(A \subseteq C\).
What is a direct proof?
If a graph contains exactly 3 vertices with odd degree, then the graph contains an Euler circuit.
What is True? (Because this hypothesis is false for all graphs)
The negation of the converse of the contrapositive
What is \(\neg P \wedge Q\) or \(\neg (\neg P\rightarrow \neg Q)\)?
The number of 4-letter words in which the letters are in alphabetical order with no repeats.
What is \(\binom{26}{4}\), or 14950?
\(\sum_{k = 0}^{10} \binom{10}{k}\)
What is \(2^{10}\)?
Used to establish an implication \(P \rightarrow Q\) by first assuming \(\neg Q\).
What is a proof by contrapositive?
True or False.
What is True?
An equivalent disjunction.
What is \(\neg P \vee Q\)?
The number of 4-letter words which use all of the letters in "for" (and no others).
What is \(36\), or \({4 \choose 2}\cdot 3!\)?
A binomial coefficient equal to the sum of the first 10 triangular numbers.
What is \(\binom{12}{3}\)