This post appears long and frightening, but I hope you will not be put off, because the topic is not actually hard to understand. It is long because I explained a lot of things from first principles. I did this because I thought the answer would be of interest to a general audience and because the branch of mathematics is not that well-known. So there is a lot of explanation, but not much is difficult.
First, a disclaimer. Graham's Number is usually cited as the largest number ever to appear in a mathematical proof. There is no evidence for this, and in fact the claim is false on its face, because Graham's Number does not actually appear in the proof that it is claimed to appear in. (It can't be the largest number ever to appear in a mathematical proof if it doesn't actually appear in a mathematical proof.) According to these posts by John Baez [1] [2]:
I asked Graham. And the answer was interesting. He said he made up Graham's number when talking to Martin Gardner! Why? Because it was simpler to explain than his actual upper bound - and bigger, so it's still an upper bound!
Martin Gardner then wrote about the number that Graham described, which is not the number from the proof, and the rest is history.
Now what is the number from the proof? Here there is some interesting mathematics.
The question addressed by Graham's Number belongs to the branch of mathematics known as Ramsey theory, which is not at all hard to understand. It can roughly be described as the study of whether a sufficiently large structure, chopped into pieces, must still contain smaller structures. This is a rather vague explanation, so I will give two of the canonical examples.
Ramsey's theorem. Let $n$ and $k$ be given. Then there exists a number $R(n;k)$ such that, if you take a complete graph of at least $R(n;k)$ vertices, and color its edges in $k$ different colors, then there must be a complete subgraph of $n$ vertices whose edges are all the same color.
A frequently-cited special case of this theorem says that $R(3;2) = 6$: if you have a party with at least 6 guests, then there must be 3 guests who have all met one another before, or 3 people who have never met; it is impossible that every subset of three guests has both a pair of people who have met and a pair of people who have not. (With only five guests, this is possible.) Here the two “colors” are “have met before” and “have not met before”.
Van der Waerden's theorem. Let $n$ and $k$ be given. Then there exists a number $W(n;k)$ such that, if you take an arithmetic progression of length $W(n;k)$, and color its elements in $k$ different colors, it must contain an arithmetic progression of $n$ elements that are all the same color.
In both these examples you can see the general pattern: we have some large structure (a graph of $R(n;k)$ vertices in one case, an arithmetic progression of $W(n;k)$ elements in the other) and we divide the structure into $k$ parts and ask if one of the parts still contains a sub-structure of size $n$.
The proofs of these theorems are constructive. For example, the proof of van der Waerden's theorem allows one to calculate that for $W(3;2) \ge 325$ suffices: if you color the integers $\{1, \ldots, 325\}$ with $k=2$ colors, then there must be an $n=3$-term arithmetic progression whose elements are all one color, and the proof shows you how to take an arbitrary coloring of $\{1, \ldots, 325\}$ and explicitly find the $3$-term subprogression of all one color.
But the $\{1, \ldots, 325\}$ is rather silly, because in fact the same is true of $\{1, \ldots, 9\}$, as is easily shown. So the proof gives an upper bound of $325$ when the correct answer is $9$. This is typical of theorems in Ramsey theorem: the proof tells you that the number exists and is at most some large number, but then closer investigation reveals that it is really some considerably smaller number. The corresponding overestimate for $W(3;3)$ is that the proof tells you that $$W(3;3) \le 7\cdot\left(2\cdot3^7+1\right)\left(2\cdot3^{\left(2\cdot3^7+1\right)}+1\right),$$
a number with $2095$ digits, but exhaustive computer search quickly reveals that actually $W(3;3)=27$.
The reason for these rapidly-growing bounds is that typically the proofs proceed by induction, and one shows that if there are sufficiently many size-$n-1$ structures, then two of them must have their subcomponents colored exactly the same, and this allows one to find sub-parts of those size-$n-1$ structures that work together to form a size-$n$ structure of all one color. But a size-$n-1$ structure with $S(n-1)$ subcomponents will have something like $k^{S(n-1)}$ ways its components can be colored, so “sufficiently many” means something like $k^{S(n-1)}$, and the number required looks something like an exponential tower of $k$'s of height $n$, that is something like $\left.k^{k^{⋰^k}}\right\} \text{height $n$}$; you can see this happening in the $W(3;3)$ example above, where the third factor is an embellished version of $3^{3^3}$. When the structures one is forming are more complicated, then instead of needing only two size-$n-1$ structures colored the same, one might need an increasingly large number of such structures, and so perhaps you can imagine how the number required increases even faster than an exponential tower.
(That was the crucial paragraph that really answers your question, so I apologize for being so vague; please let me know if you want me to elaborate or provide a specific example.)
Enormous numbers are quite commonplace in Ramsey theory, and so the Graham's Number might have some competition even in its own field.
The particular problem discussed in
the Graham's Number paper, “Ramsey's theorem for $n$-parameter sets” is rather general, but the enormous number (not the one described by Gardner) is an upper bound for a problem very similar to the ones I described above:
We recall that by definition $N(1, 2, 2)$ is an integer such that
if $n\ge N(1, 2, 2)$ and the $\binom{2^n}{2}$ straight line segments joining all possible pairs of vertices of a unit $n$-cube are arbitrarily 2-colored, then there always exists a set of four coplanar vertices which determines six line segments of the same color.
That is, Graham and Rothschild are investigating a problem that, in this special case, involves taking a certain $n$-dimensional object, coloring its 1-dimensional subobjects with 2 colors, and looking for a single-colored 2-dimensional subobject; $N(1,2,2)$ is the smallest number of dimensions that such an object must have in order to guarantee a single-colored 2-dimensional subobject.
Let $N^*$ denote the least possible value $N(1,2,2)$ can assume.
We introduce a calibration function $F(m,n)$ with which me may compare our estimate of $N^*$. This is defined recursively as follows:
$$\begin{align}
F(1,n)=2^n \qquad F(m,2)=4 &\qquad m\ge 1, n\ge 2, \\
F(m,n) = F(m-1, F(m,n-1)) & \qquad m\ge2, n\ge 3.
\end{align} $$
It is recommended that the reader calculate a few small values of $F$ to get a feeling for its rate of growth, e.g. $F(5,5)$ or $F(10,3)$.
“A few small values” here is a joke. $F(3,3)$ is already $2^{16}=65536$. $F(3,4)$ is a tower $2^{2^{⋰^2}}$ of height $65536$. $F(3,5)$ is a similar tower of height $F(3,4)$.
Finally, the bound:
The best estimate we obtain this way is roughly
$$N^* \le F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).$$
The authors continue with an understatement that I imagine made them chuckle:
On the other hand, it is known only that $N^*\ge 6$. Clearly, there is some room for improvement here.
A remark a little later says
in fact, the exact bound is probably $<10$.
but Sbiis Saibian's excellent discussion of this claims, unfortunately without citation:
It was recently proved that the solution could not be smaller than $11$.
I will be glad to elaborate on any part of this that is not clear.
What would the result be when this method is applied to Graham's number?
(This is very similar to an earlier question, "Logarithms of logarithms of Graham's number, is the result ever handy?".)
Answer: The method cannot be applied to Graham's number ($G$), because the number of iterations required would be too large to have its digits written on any card.
By the definition of $G$ and the properties of Knuth arrows,
$$G \ = \ 3\uparrow^{g_{63}} 3 = 3\uparrow^{g_{63}-1}(3\uparrow^{g_{63}-1} 3) \ \ggg \ 3\uparrow^{2}(3\uparrow^{g_{63}-1} 3) \ \gt \ 10\uparrow^{2}\left( \frac{3\uparrow^{g_{63}-1} 3}{9}\right)$$
where $g_{63}$ is a number with an incomprehensibly large number of decimal digits. (The rightmost inequality is by application of a simple change-of-base inequality.)
In the present problem, the number of full pages occupied by the digits of a number x is
$$f(x) \ = \ \left\lfloor \frac{\lfloor \log_{10} x \rfloor +1}{4000} \right\rfloor $$
and the number to be finally written on the card is the least number of iterations, say $n$, such that
$$f^n(G) \ \le \ 25000$$
However, it's easily verified that
$$ f(x) \ \gt \ \log_{10} \log_{10} x \quad (x \ge 10^{10^{10}}) $$
so for any number of iterations $k$ (until the tower is reduced to less than $10^{10^{10}}$),
$$f^k(G) \ \gt \ (\log_{10})^{2k}(G) \ \ggg \ 10\uparrow^{2}\left( \frac{3\uparrow^{g_{63}-1} 3}{9}-2k\right)\tag{*} $$
Therefore, long before the final iteration is reached, the number of iterations will become utterly "unwritable". For example, even for $k$ iterations, where $k$ is the "unwritable" number
$$k = 3\uparrow^{g_{63}-2} 3$$
the intermediate result, $f^k(G)$, is still enormously larger than a tower of $10$s of height
$$\frac{3\uparrow^{g_{63}-1} 3}{9}-2(3\uparrow^{g_{63}-2} 3) \ \ggg \ 3\uparrow^{g_{63}-2} 3$$
Note that $3\uparrow^{g_{63}-2} 3$ has only two less arrows than $G$ itself!
NB: Graham's number is extreme overkill for this conclusion. For example, the cartoon's method cannot be applied to any number $x$ greater than or equal to, say, $10\uparrow\uparrow{(10\uparrow\uparrow5)}$, because the lefthand inequality in (*) above (with $x$ replacing $G$) will then show that $f^k(x) \ \gt \ 10\uparrow\uparrow4$ even for $k > 10\uparrow\uparrow4$ iterations. ($10\uparrow\uparrow4$ is "unwritable" in the sense of having more decimal digits than will fit in the observable universe, assuming at least one Planck volume per digit.)
Best Answer
I'm about to prove that Graham's number is a number that is so big there is no way of intuitively grasping the magnitude of it, but in order to do this we must start with the very small and work our way up.
We will start with the number 9 which can represented as 3+3+3. This isn't so bad when you only have three 3's to write down, but what happens if I pick a number that isn't practical to be represented by +3's, like 729, I would need the sum of 243 3's, so now let's use multiplication. 729 can now be represented as 3*3*3*3*3*3 now I can represent larger numbers than before, but I run into the same problem. I can pick a number that isn't practical to be represented by the repetition of the same operator of multiplication.
7,625,597,484,987, for example, is the multiplication of 27 3's. That isn't good way to represent this number so now let's use powers to represent this number which is $3^{3^3}$, another way to represent this is $3 \uparrow 3 \uparrow 3$ where each single arrow is "to the power of operator".
Mathematicians realized when dealing with numbers that aren't practical to write down in one operator, a new operator is required that is more powerful the previous one. Arrow notation is a way of going from one operator to another with ease. $\uparrow \uparrow$ is the next operator up from $\uparrow$, just as $\uparrow$ is the next operator up from multiplication, and just as multiplication is one operator up from addition. So increasing the number of consecutive arrows will increase the ability to work with larger and larger numbers.
So we saw how the size of numbers that were created when using $\uparrow$. Now let's look at the $\uparrow \uparrow$. $3\uparrow \uparrow3\uparrow \uparrow3$ = $3\uparrow \uparrow(3\uparrow3\uparrow3)$=$3\uparrow \uparrow7,625,597,484,987$. Which means this is $\uparrow3$ is used on 3, 7,625,597,484,987 times!
${{{{{{{{{{3}^3}^3}^3}^3}^3}^3}^3}^3}^\cdot\Rightarrow}$ a stack of threes 7,625,597,484,987 high!
To calculate this value start with the top 3 and move downward.
$3^3 = 27$
$3^{27}=7,625,597,484,987$
$3^{7,625,597,484,987}$ is 3,638,334,640,024 digits long.
The fourth 3 is very large, but googolplex is 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 digits long. So still somewhat in our comprehension, but the fifth 3 is way out of our comprehension.
3 is raised to the power of a number that is 3,638,334,640,024 digits long.
Googolplex is 10 raised to the power of a number that is 101 digits long.
So we have used only 5 of the 3's on the 7,625,597,484,987 stack and it already becomes difficult to imagine, but this process is repeated over 7.6 trillion times. Doing this process 5 times took us from 3 to a number that makes googolplex look tiny. So the answer to the stack of 7,625,597,484,987 3's is a stupidly big number. This number is so big that if you memorized all the digits of this number your head would turn into a black hole. The maximum amount of entropy that can be stored in your head carries less information than the information of this stack of 3's.
[ http://m.youtube.com/watch?v=XTeJ64KD5cg ]
$$ \begin{array}{c|l|c|r} \text{operator representation} & \text{value} & \text{number of previous operator equivalent} \\ \hline 3*3*3 & 27 &\text{9 (+3)'s or 3+3+3+3+3+3+3+3+3}\\ 3\uparrow3\uparrow3& 7,625,597,484,987 &\text{27 (x3)'s or $3^{27}$} \\ 3\uparrow\uparrow3\uparrow\uparrow3 & \text {stupidly big} & \text{7,625,597,484,987 ($\uparrow$ 3)'s}\\ 3\uparrow\uparrow\uparrow3\uparrow\uparrow\uparrow3 & G_1 & \text {stupidly big ($\uparrow\uparrow3$)'s} \\ \end{array} $$
If you look at the table above you will notice that $3\uparrow\uparrow\uparrow3\uparrow\uparrow\uparrow3=G_1$.
Why is $G_1$ important? Well I'll get to that in a minute. But first I have to explain that each change from one operation to the next is unimaginably bigger than previous change so you would think that adding a few arrows would quickly get us to Graham's number, but it doesn't. It doesn't even come close.
So what if I were to put a subscript on the arrows to indicate how many arrows I have. So $3\uparrow_{1000000}3$ is one million arrows, so I am one million operations above multiplication and 999998 operations above "stupid big" and the value of each operation is unimaginably bigger than the previous one. So, surely I must have hit Graham's number by now. The answer is no.
Remember $G_1$? Well, I'm going to write this, $3\uparrow_{G_1}3$.
So let's see if I can break this down.
"stupidly big" made googolplex look tiny after 5 of 7,625,597,484,987 iterations. Applying $\uparrow\uparrow3$ to 3 "stupidly big" times gives me $G_1$ and $G_1$ is now going to be the number of times the operator is increased. Where each operation is unimaginably bigger in comparison to the previous one. So how well do I stand against Graham's number at this point? Not even close.
Finally,
$G_2$=$3\uparrow_{G_1}3$
$G_3$=$3\uparrow_{G_2}3$
$G_4$=$3\uparrow_{G_3}3$
$\vdots$
$\vdots$
$G_{64}$=$3\uparrow_{G_{63}}3=\text{Graham's number}$