**Finite Form of The Graph Minor Theorem**

Friedman, Robertson & Seymour (1987) showed that the following theorem exhibits the independence phenomenon by being *unprovable* in various formal systems that are much stronger than Peano arithmetic, yet being *provable* in systems much weaker than ZFC:

**Theorem**: For every positive integer*n*, there is an integer*m*so large that if*G*_{1}, ...,*G*_{m}is a sequence of finite undirected graphs,- where each
*G*_{i}has size at most*n*+*i*, then*G*_{j}≤*G*_{k}for some*j*<*k*.

(Here, the *size* of a graph is the total number of its nodes and edges, and ≤ denotes the minor ordering.)

Read more about this topic: Robertson–Seymour Theorem

### Famous quotes containing the words finite, form, graph, minor and/or theorem:

“The *finite* is annihilated in the presence of the infinite, and becomes a pure nothing. So our spirit before God, so our justice before divine justice.”

—Blaise Pascal (1623–1662)

“Average American’s simplest and commonest *form* of breakfast consists of coffee and beefsteak.”

—Mark Twain [Samuel Langhorne Clemens] (1835–1910)

“When producers want to know what the public wants, they *graph* it as curves. When they want to tell the public what to get, they say it in curves.”

—Marshall McLuhan (1911–1980)

“For a country to have a great writer ... is like having another government. That’s why no régime has ever loved great writers, only *minor* ones.”

—Alexander Solzhenitsyn (b. 1918)

“To insure the adoration of a *theorem* for any length of time, faith is not enough, a police force is needed as well.”

—Albert Camus (1913–1960)