UMBC CMSC203, Discrete Structures, Spring 2009

Existence Proofs

An existence proof establishes the existence of a mathematical object with some properties we desire. Existence proofs may be constructive or non-constructive. A constructive proof explicitly specifies the object. Here, the specification can be mathematical --- infinite objects do not have to be written down. Non-constructive existence proofs only show that the desired object exists. Some examples will clarify this concept.

Example 1: In the section on proof by contradiction, we used a graph that was not 3-colorable. This graph has triangles --- 3 vertices that are connected to each other. For example, vertices a, e and c form a triangle:

It was very useful to have triangles in our argument that the graph is not 3-colorable, because the 3 vertices in a triangle have to be colored with 3 different colors. Are triangles necessary to prove that a graph is not 3-colorable? No.

Claim: There exists a triangle-free graph that is 4-colorable, but not 3-colorable.

Proof: Consider the following graph and its 4-coloring: By checking every triple of vertices, the reader can verify that the graph is triangle-free. We leave the proof that the graph is not 3-colorable as an exercise.
QED

Example 2: The proof in the previous example is definitely constructive. The graph with the desired property is given explicitly. In this example we prove the existence of a number with certain properties without saying which number has the property.

Claim: There exist irrational numbers x and y such that x^y is rational.

Proof: Let z = √2 ^√2. If z is rational then z is our desired number with x = √2 and y = √2.
Now, suppose that z is irrational. Then, let x = z and y = √2.
x^y = (√2 ^√2) ^√2 = √2 ^{(
√2 ⋅
√2
)} = √2 ² = 2.
In this case, x^y is again rational.
In either case, whether z is rational or irrational, we've shown the existence of irrational numbers x and y such that x^y is rational.
QED

The proof in Example 2 is definitely non-constructive. The proof establishes the claim but does not tell us if it is √2 ^√2 or (√2 ^√2) ^√2 that is rational. Generally speaking, non-constructive proofs are less satisfying than constructive proofs. In computer science, especially, constructive existence proofs are preferred because we often want to use the desired object in a program or algorithm. A non-constructive proofs would not help there.

⇐ Proofs by Contradiction

Proof by Cases ⇒

Last Modified: 22 Jul 2024 11:28:07 EDT by Richard Chang

to Spring 2009 CMSC 203 Homepage