Elementary+Short+Useful Imagine your-self in front of a class with very good undergraduates 
who plan to do mathematics (professionally) in the future.
You have 30 minutes after that you do not see these students again.
You need to present a theorem which will be 100% useful for them.

What would you do? 

One theorem per answer please. Try to be realistic.
For example: 30 min is more than enough to introduce metric spaces, 
prove existence of partition of unity,
and explain how it can be used later.
P.S. Many of you criticized the vague formulation of the question. I agree. I was trying to make it short --- I do not read the questions if they are longer than half a page. Still I think it is a good approximation to what I really wanted to ask. Here is an other formulation of the same question, but it might be even more vague.
Before I liked jewelry-type theorems; those I can put in my pocket and look at it when I want to. 
Now I like tool-type theorems; those which can be used to dig a hole or build a wall. 
It turns out that there are jewelry-type and tool-type theorems at the same time. 
I know a few and I want to know more.
 A: Introduce generating functions and give couple of applications.
A: The Banach fixed point theorem.
A: Stokes' Theorem
A: The Archimedes proof that the uniform distribution on the sphere projects on the uniform distribution on a diameter.
A: Singular Value Decomposition, probably one of the most useful and ubiquitous concepts out there. Half the time can be devoted to listing all the synonyms it goes by in various fields such as statistics and finance. 
A: Sperner's lemma (Two-dimensional case)
A: The definition of the tensor product and existence/uniqueness/associativity properties.
I know, this is perhaps not a single theorem but in my eyes one of the most useful "elemetary" concepts. Personally, I had two semesters of linear algebra without mentioning the tensor product. And from this I suffered for a long time during my further studies. Now it is my first homework/exercise for students in my lectures (e.g. diff geo).
If the student is really clever, one can even do something like the tensor algebra in these 30 min.
A: I would introduce Bezout's Theorem (there is an article on wiki).
It will be hard to prove this statement in the full generality, but the proof of the weaker statement:
The system of two polynomials $P(x,y)$ and $Q(x,y)$ without common factors of degrees $m$ and $n$ correspondingly has at most $mn$ solutions.
takes one page at most and uses only the fact that polynomials of two variables have a unique factorisation in irreducible polynomial. (for example, you can check page 244 in an appendix of the book "Rational Points on Elliptic curves" of Silverman and Tate).
The well-known beautiful (or, say, elementary) application of this theorem is Pascal's theorem. 
A: I would say something far far more elementary than all the other suggestions here (perhaps assuming the audience is in their first semester as undergraduates)
I would define an equivalence relation and an equivalence class and prove that equivalence classes on $X$ define a partition of $X$. (And then spend the remaining 29 minutes talking about their philosophical significance :) )
Its usefulness is of course immense but that doesn't mean we should attribute it solely to its obviousness. In my mind it also encodes so many very deep intuitions that separate high-school from college-level mathematics. To name a few: 


*

*The fact that there is nothing metaphysically 'special' about the relation of equality, which foreshadows the algebraic paradigm-shift towards isomorphisms

*The fact that information about certain properties is better captured when we look at classes of objects satisfying a relation

*That the foundations of analysis are a lot more conceptually flexible (and amenable to reinterpretation or even reinvention) than 'functions and derivatives'.

*The information encoded by the definition of an equivalence relation is absolutely minimal and trivial to understand (which is why most undergraduates, I've found, almost scoff when a lecturer spends time defining it) and yet responsible for profoundly deep intuitions - think of the Grothendieck group.

*It brings out the significance of structuralist thinking at a very early, pre-algebraic stage (this is more personal, but still)

A: Compactness of First Order Logic (using ultraproducts, not as a corollary of completeness; they get Łoś's Theorem for ultraproducts as a freebie.)
A: The well-ordering theorem and an application (that uses transfinite recursion, after well-ordering a set). Many interesting sets and examples can be built that way. Or maybe Axiom of Choice/Zorn's lemma (show one from the other) and then show the well-ordering theorem.
A: Uniform convergence of the averages of the partial sums of the Fourier series, for any continuous function $f$ on $[0, 2 \pi]$ with $f(0)=f(2\pi)$:
$$ \sigma_N(f, \theta) = \sum_{n = -N}^N \left(1-\frac{|n|}{N+1} \right) \widehat{f}(n)e^{in \theta} \to f(\theta)
$$
And the Weierstrauss Polynomial Approximation Theorem: the polynomials are uniformly dense in $C[a,b]$. This is a corollary of the Fourier series result, or it can be proved similarly. Finally, if time permits, the Stone-Weierstrauss Theorem.
Of course, it would be nice to talk about approximations to the Dirac Delta, convolutions, fundamental solutions to PDEs, e.g. the Heat Equation, etc. etc. but I suppose only a REALLY good class could absorb all this in half an hour...
A: Heisenberg's uncertainty principle.


*

*Everyone should be exposed to quantum mechanics.

*Appears frequently in analysis and probability (not to mention physics).  

*Showcases some of the highlights of Fourier theory.

A: Theorem. $\sqrt{2}$ is irrational.
This is an ancient theorem, about 2400 years old, and its modern proof is identical to the one appearing in Euclid's elements. A simple number theoretic proof, where you get the chance to use the abductio ad absurdum (or εἰς ἄτοπον ἀπαγωγή).
Note. As Victor Protsak noted, the number-theoretical proof is not the first one. The first one is believed to geometrical, using anthyphaeresis (ἀνθυφαίρεσις), i.e., proving geometricallly that the euclidean algorithm of dividing $1+\sqrt{2}$ by $1$ is periodic:
\begin{align}
1+\sqrt{2}&=2\cdot 1 +v_1, \\
1&=2\cdot v_1+v_2, \\
v_1&=2\cdot v_2+v_3, \\
\text{etc}
\end{align}
and thus $1+\sqrt{2}$ and $1$ are inconsummerable (ἀσὐμμετρα). It is noteworthy that, although the number theoretical proof appaears Euclid's Elements, which were written c. 300 BC, the fact that there is a proof that the square roots of positive integers less than 19 is mentioned in Theaetetus of Plato, writeen c. 380 BC. Anthyphaeresis works for every $n$, but it can get extremely complicated, as $n$ gets larger. In fact, for $n=19$, in order to establish periodicity of Euclidean algorithm, 6 steps are required, and huge geometrical figures to observe it! A few years ago I supervised a Master's thesis on this proof, and I think it makes an extremely interesting lecture.
A: Combinatorial Nullstellensatz. You may prove it and then choose your favorite applications for as many minutes as you have. I personally like to include applications to evaluation of coefficients, as explained in this MO answer, after that to additive combinatorics, like Cauchy--Davenport theorem, and to graph theory, like 3-choosability of a planar bipartite graph. 
A: Series representations for functions and the fact that $\mathbb C$ is "rigid" in contrast to 
$\mathbb R$ when discussing differentiability and series developements.
This "explains" for example how pocket calculators compute trigonometric functions, logarithms and exponentials.
A: Gödel's incompleteness theorems
A non-technical overview could be done in a fairly short amount of time, thus allowing for some discussion of its various implications, particularly regarding possible roles of mathematics.
A: How about the probabilistic method?
There are plenty of elementary, self-contained examples to choose from, and it has a pithy slogan that's memorable enough even for non-combinatorialists. (Can't construct something explicitly? Then construct it randomly!) Best of all, it has a nice wow factor: While many undergraduates may be familiar with nonconstructive phenomena in mathematics, the fact that we need to resort to such to say things about finite graphs is rather surprising.
A: Euler's formula $V - E + F = 2$.
A: Edit (Feb 2021): The content of this MathOverflow answer now forms the backbone of Chapter 2 ("Multiple Proofs") in JDH's book, Proof and the Art of Mathematics. Get a copy!

Edit (Dec 2016): Encouraged by a few comments on MO, and a few direct emails about this post, I wrote up the ideas below for a journal of math education. The citation is:

Dickman, B. (2017). Enriching Divisibility: Multiple Proofs and Generalizations. Mathematics Teacher, 110(6), 416-423. Link (no pay-wall).


Having come across this question by searching within the mathematics-education tag, I will try to answer it from the perspective of someone in the field of Mathematics Education.
Theorem: $n^2 - n$ is even for all natural numbers $n$.
It is quite possible that very good undergraduates (I am imagining freshmen) will laugh at seeing such a "theorem" written on the board; it is almost certain that professional mathematicians will scoff. Nevertheless, this is a talk that I have given in the past to graduate students in Math Education who wish to teach secondary school mathematics in the future. Under some reasonable interpretation of the parameters given in this question, I should think these two groups alike enough to outline the talk here.

After writing the theorem on the board, I then write down a collection of headers, each of which is intended as suggesting a method of proof. Once the headers are written out, I give the students three minutes to prove the theorem using one method that they are sure they can carry out, and to attempt a proof using another method they are less sure of. Below I will write the headers, followed parenthetically by the sort of remark I might say aloud as I write them down, and then a brief indication of the proof.
Cases: (Probably you don't need more than two) The cases I am thinking of are even and odd; check what happens when $n = 2k$ and then check what happens when $n = 2k+1$.
High School Algebra: (Factoring) Write $n^2 - n = (n-1)n$ as the product of consecutive integers, hence once of them must be even; so the product is even.
Number Theory: (This might not mean so much to you all as freshmen; we'll return to it later!)
Arithmetic: (I'm thinking of adding up a certain arithmetic sequence) Consider the sum of the first $n-1$ natural numbers; this gives some natural number $k = (n-1)n/2$. Multiplying both sides by $2$, we find that $n^2 - n = (n-1)n = 2k$ is even.
Geometry: (How would you represent $n^2$ with a geometrical picture?) Consider an $n \times n$ array of squares; remove the $n$ squares along the diagonal. The number of squares remaining is $n^2 - n$ and one sees symmetrically that they have been split into two groups of equal size. Hence the total is even.

Combinatorics: (I'm thinking of forming two person committees...) The number of two person committees in a group of $n$ people is some integer $k = (n-1)n/2$. Cf. Arithmetic.
Mathematical Induction: (For students familiar with induction, you might give this a shot) The base case is clear; suppose $k^2 - k$ is even and note $(k+1)^2 - (k+1) = k^2 + k = (k^2 - k) + 2k$ is the sum of two even numbers, and hence even.

The point of the above is to demonstrate that even a seemingly simple statement can be proved in a number of different ways. Such a demonstration, more than any particular theorem, is likely to be useful for all students (as specified by the OP). I usually have students discuss their answers and then use the theorem we've proved to talk about something else that ought to be useful for everyone: generalization.
The proofs above made frequent use of the following fact: $(n-1)n = n^2 - n$.
How would you generalize the following statements?
Statement A: If $n \in \mathbb{N}$, then $2$ divides $(n-1)n$.
Statement B: If $n \in \mathbb{N}$, then $2$ divides $n^2 - n$.
The former statement suggests (in my mind) that $k$ divides $k$ consecutive numbers; the latter statement suggests (in my mind) that $k$ divides $n^k - n$.
Consider when $k = 3$.
Then the statements become:
Statement A: If $n \in \mathbb{N}$, then $3$ divides $(n-1)n(n+1)$.
Statement B: If $n \in \mathbb{N}$, then $3$ divides $n^3 - n$.
Not only are these statements true, they coincide: $(n-1)n(n+1) = n^3 - n$.
This overlap breaks down for $n>3$, though, and we find that only A is true for $n=4$. (Perhaps a good point at which to mention how a single counterexample can disprove a for all statement.)
From here, the talk suggests that A is a good segue into modular arithmetic, while B practically begs us to find the $k$ for which it holds. Of course, we can answer this question using Number Theory (as mentioned early on!) and, more precisely, by appealing to Fermat's Little Theorem.

I believe the talk outlined above, with its messages about the possibility of finding multiple proofs and the interesting directions in which a simple proposition can be generalized, is a practical and doable thirty minute talk for first-year students in mathematics. I have done nothing close to applying Groebner bases or making use of ultraproducts, but I have tried to heed the OP's request to be realistic.
A: The Chinese Remainder Theorem. This is ripe for giving some nice applications, some of which are given in this MO thread (hat tip to Pete Clark; I presume this is the one he meant). 
A: The Central Limit Theorem.
A: Hilbert projection theorem
A: *

*The famous Heine - Borel theorem which says that a closed a bounded subset of $\mathbb{R}^{n}$ is compact.

A: [I would introduce Taylor's theorem and point out that it has many applications for instance in physics but also in differential geometry. On the one hand very elementary proofs can be given, but on the other hand, for practical computations with "nice" functions it is always helpful to have that theorem in full generality at the ready. For instance in Riemannian Geometry, one uses Taylor expansion in combination with Jacobi fields to expand the metric tensor locally. This does show that locally, we can find coordinates s.t. the metric behaves like the standard Euclidean metric, but there have to be some corrections such as one term involving the Riemannian curvature tensor.][http://en.wikipedia.org/wiki/Taylor's_theorem]
A: Moore closures, their relation to collections of Moore-closed sets and a characterization for closure under finitary operations. 
One can then discuss why Moore-closed sets form a complete lattice and a lot more, if one feels so inclined.
This is certainly something students will encounter over, and over, and over again in different guises. Moore-closures are certainly among the most useful trivialities I know.
A: The Pigeonhole Principle
A: Maybe (a suitably weak version of) Brouwer fixed point theorem? For example you can prove the version for smooth maps, or the topological version in low dimensions. And there are so many generalizations of the theorem that it seems the students are bound to run into some version of topological fixed points in the future. 
You can even mention, as an application of topological fixed points, Littlewood's proof that there always exists a way to put a rod standing on one end in a train travelling between Kings Cross and Cambridge such that it would not fall over. (In fact, isn't that entire chapter of the Miscellany [Chapter 1, Mathematics with minimum raw material] consisting of answers to your question?)
A: Let $G$ be a finite group and $V_i$, $i=1,...,r$ be the irreducible representations, $d_i:=dim(V_i)$. Then $|G|=\sum_i d_{i}^{2}$.
A: Sanov's theorem of large deviations.  
I don't have to prove anything, right?  If they want a proof, they'll look it up in a book later.  
Assume the students already know about the central limit theorem.  Explain how the two theorems talk about limits in different direction: let $ S_n $ be the sum of $ n $ independent variables of identical distributions (real valued, with zero mean and finite variance), the central limit theorem gives a limit of the unscaled probability $ P(S_n/\sqrt{n} < c) $, this limit is strictly between 0 and 1; whereas large deviation theorems give the rate of decrease of a probability like $ P(S_n/n < c) $.
A: I've always been thrilled by the fact that the coefficients of a (monic) polynomial are obtained by taking the elementary symmetric functions in (minus) the roots of that polynomial:
$$\prod_{i=1}^n (X+\alpha_i) = \sum_{k=0}^n (\sum_{i_1 < \cdots < i_k} \alpha_{i_1} \cdots \alpha_{i_k})X^{n-k}$$ 
A lot is built on this, I think. I'd like to explain the connection to automorphisms and fixed fields and how the roots of a polynomial are permuted by an automorphism that fixes the coefficient field of that polynomial. Then maybe mention the beginnings of Galois theory.
A: At the risk of incurring the wrath of some here, I would propose the Yoneda Lemma, along with the minimum of necessary category theory. Like it or not, category theory is hugely useful to algebraists, and early exposure can be very helpful. (It was to me!)
A: The Martingale stochastic process
A: I would tell them "What is real maths". 
To achieve this use Lakatos way about Euler's formula ( $ V - E + F = 2 $ ).
It is a set of successive reformulations (more and more precise) each followed by a counter example justifying the next reformulation. 
Reference is : I. Lakatos, "Proofs and Refutations: The Logic of Mathematical Discovery
A: The Arithmetic Mean-Geometric Mean Inequality.
A: My suggestion -- assuming they have not yet taken a class on complex analysis -- would be to talk about Eulers formula  and De Moivre's formula, along with the complex representations of the most common trigonometric functions. Perhaps, if there is time left, power series and the Cauchy product could be touched upon.
This could help the students to understand better how some trigonometric identities can be derived, which is usually not explained in detail until a first course on complex analysis. 
Each of the topics is simple enough to introduce in a very short amount of time, so there would probably be time left to show some cool applications.
A: Cauchy's integral theorem and Cauchy's integral formula.
It's really an example of a jewellery-type and tool-type theorem at the same time. It can be introduced and proved for students that even don't know about functions of complex variables in 20 minutes. And other 10 minutes can be spend to say how many applications and generalizations these results have in theory of functions and applied mathematics.
A: I am surprised that no one mentioned the Baire category theorem.
I am not sure if you would have enough time to show many applications in 30 minutes but it is almost certain that they will end up using it at some point. Here are some applications discussed on MO.
A: Existence of Nash equilibria. This is feasible in 30 minutes, and builds surprising connections between game theory, elementary probability, elementary geometry, and algebraic topology.
A: Newton's method for solving the non-linear (systems of) equations. How to make the presentation depends on the level and interests of the students. It can range from a fast algorithm for finding the square root with high precision to some advanced topics in dynamics. 
A: Picard–Lindelöf theorem on existence and uniqueness of solutions to ordinary differential equations, introducing Picard iteration along the way. 
A: The Arzelà-Ascoli theorem.
A: A short presentation on the  Hopf fibration  could be very useful as it is such a central example.  The idea to make it elementary would be to take a concrete point of view and include lots of pictures.  
A: Hall Marriage theorem
This is a very useful theorem in combinatorics, analysis, algebra, computational complexity, and more.
A: Using Groebner Bases to solve equations.  Just use the lexicographic ordering without disucssing theory.  Mash generalized polynomial long division and Buchberger's algorithm into one mechanical procedure. 30 minutes is pretty tight, but doable.
A: Completeness theorem for first order logic.
A: Stone's representation theorem.
A: The Gelfand-Naimark theorem: every commutative C* algebra is $C_0(X)$ for some locally compact Hausdorff space $X$.  


*

*The spectral theorem is a corollary.

*The theorem introduces students to the idea that a ring is a geometric object

*Certain constructions in topology, e.g. the Stone-Cech compactification, become more transparent.

A: My first choice was taken, Picard iteration using Fixed point principles. I'll try not to have a repeat. I have been teaching a history of math class this semester so this sort of thing has been on my mind recently.
I would definitely consider different choices depending on how advanced the students I expected were.
Pre-Calculus but talented: Archimedes method for finding $\pi$.
Calculus: Fermat method for finding the integral of $x^n$ 
Differential Equations: Picard iterations/fixed point principles
more advanced. The Brachistichrone.
Another topic that I like, specifically for analysis is to take some of the different definitions of continuity and show that they are equivalent.
A: I can just imagine what would have happened if I was introduced to Kepler's Conjecture and Thomas Hales' approach earlier ...
A: Pursuant to Johannes's answer, I would like to give a talk entitled “How to factor $x_0^4 + x_1^4 + x_2^4 + x_3^4 - 2x_0^2 x_1^2 - 2x_0^2 x_2^2 - 2x_0^2 x_3^2 - 2x_1^2 x_2^2 - 2x_1^2 x_3^2 - 2x_2^2 x_3^2 - 8x_0 x_1 x_2 x_3$”.
A: Schur's Lemma. After which one can as an application, classify the simple modules for cyclic groups.
A: Fundamental Theorem of Finitely Generated Abelian Groups.
A: Integration by Parts
It's a powerful analytical tool and it can be used for reduction of order on complex functions.
A: Jordan normal form.
A: Tarski's fixed point theorem.
A: Borsuk-Ulam theorem. A very useful topological theorem. It is very easy to state and to describe some applications, or alternatively to describe what is involved in a proof. 
A: Strong law of large numbers
A: Lagrange's theorem (order of a sugroup divides the order of the group).
A: Simplicity of the alternating group An for $n\geq 5$, contrasted with its non-simplicity for $n\leq 4$.
A: Elementary symmetric polynomials generate the ring of symmetric polynomials.
A: Quite unbelievable that I haven't seen that answer in the previous ones.
Cantor's Theorem & Cantor's Diagonal.
Both of these are quite short, and one can squeeze them into a 30 minutes discussion including the definition of "cardinality".
I find them useful, even if not directly applicable, the shock that infinite objects (and generally, mathematical objects) need not match our finite intuition is probably one of the most important things that new mathematicians should learn. When you know that you don't know what to do, you work with the definitions slowly and carefully and eventually you develop the intuition that allows you to run freely in the field.
A: Min-max principle and spectral theorem as a corollary for real symmetric matrices.  I often teach this quickly in my vector analysis course as an example of finding extrema of functions in $\mathbb{R}^n$. 
A: The spectral theorem for normal operators.
A: Okay, last one from me tonight. 
Separating hyperplane theorem and/or the Riesz extension theorem. The finite (or 2) dimensional version is fairly easy to illustrate and not too hard to prove. And of course as an example application you can assume the infinite dimensional version and derive Hahn-Banach Theorem (the version about extending linear functionals). Consider its use in convex and functional analysis, at least some of the students will run into something like this in the future. 
A: Robinston-Schensted-Knuth algorithm
This is a map between permutations to pairs of standard tableaux. So it immediately gives various wonderful facts. It is elementary, short and useful.
A: The isoperimetric inequality.


*

*Ubiquitous in geometry.

*Among the easier examples of variational problems.

*Can be used to illustrate why we need rigorous proofs of things that are "obvioius".

A: Helly theorem. It is easy to motivate state and prove in 30 minutes. It is very useful in terms of application as a fundamental example of a result in combinatorial geometry.
A: Maybe a stretch, but...
Finiteness of the class number via Minkowski's theorem.


*

*Everyone should at least have a rough idea what the class number is.

*Minkowski's theorem has other amusing and useful applications (e.g. well-definedness of the signature?)

*One of the first (of many) interesting theorems involving the geometry of lattices.

A: Sperner's Theorem on antichains in subset lattice and the Sunflower Lemma. Two great theorems in combo which require little to no theory to introduce and have extremely beautiful proofs. 
A: *

*I would go for Cayley's theorem which asserts that every group is isomorphic to a subgroup of $S_{n}$ for some $n$. 


One, can even look into this following post:


*

*https://math.stackexchange.com/questions/10029/importance-of-cayleys-theorem
A: Consider some metric spaces, then
Hausdorff distance and Gromov-hausdorff convergence
Also, introduce catagorical notation, it may be very useful.
A: Riesz theorem or, more general, Lax-Milgram theorem.
A: The Laplace approximation to integrals!  This scores well on all points: it is elementary (could be taught in calculus 1) and very useful. Within 30 minutes there should be time to some application, dependent on the audience, maybe the Stirling approximation to the factorial (which is often useds without any proof).
A: In a metric space context, using natural metric, construct reals as equivalence classes of Cauchy sequences of rationals.
A: Every matrix can be represented by the linear combinations of four orthogonal matrix
A: Yoneda Lemma. :D
A: Something that I found very interesting and very useful is Singular value decomposition.
It shows that every operator is "almost diagnosable", and is skipped in a lot of basic linear algebra courses I have seen.
I has many application, for example - solving sum of least squares of example. You can give a 30 minute talk on this in various levels as well.
There are prettier theorems (Stokes, Uniformization, and many more) but I think with the 3 constraints (interesting, useful, little background) this is a good topic.  
