I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful **proof for free** using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).

**Gallai's Lemma.**

Let $G$ be a connected graph such that $\nu(G-x)=\nu(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$

Remark: $\nu(G)$ is the size of a maximum matching of $G$, and def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.

**Proof for free**.
In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r(\{x,y\})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.

Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Therefore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. In particular, $V(G)$ has co-rank 1, and so def$(G)$=1, as required.

**Edit.** For completeness, I decided to include the derivation of Tutte-Berge from Gallai's lemma. Choose $X \subset V(G)$ maximal such that def$(G-X) -|X|=$ def$(G)$. By maximality, every component of $G-X$ satisfies the hypothesis in Gallai's lemma. Applying Gallai's lemma to each component, we see that $X$ gives us equality in the Tutte-Berge formula.

reallywant to discuss this, start a thread on meta about it) – Andrew Stacey May 4 '11 at 9:01