soft question - Theorems for nothing (and the proofs for free)

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.

• Next set theory - Denumerable sets
• Previous at.algebraic topology - Fiber bundle = principal bundle + fiber?