**Theorem**. For every positive integer n, .

**Proof**. Consider a tree on n vertices with root . Assign to each edge an element of the vector space , obtained by setting 1s in the the coordinates corresponding to v and w and 0s elsewhere. I claim that these vectors are linearly independent; for suppose otherwise, and letthe vectors corresponding to sum to 0. There is a natural “distance” function on E w/r/t ; let have maximal distance in S, and suppose WLOG that t is farther than s from . Then the coordinate corresponding to t is nonzero for exactly one element of S, and the sum over all elements of S must therefore be nonzero. This is a contradiction. So in particular these |E| = n-1 elements are distinct and nonzero, which means (by Pigeonhole) that there are at most of them.

Okay, so this seems like a lot of work to establish something that can be done in two lines with induction. And in fact you can view the above proof as inductive as well; if we build edge by edge, we get the necessary statement that |E| = n-1 as a bonus.

But of course that can also be established by topological methods, which means that the only “combinatorial” part of the whole proof lies in picking the basis of our vector space. And in fact that’s really all we need, the rest of the proof being more or less window dressing:

**Proof** (of Theorem). Let . Pick a basis of V. Proceed as in the end of the first proof.

So the first proof is pretty much useless. However, there are at least two ways it can be modified to be made (potentially!) interesting.

First, note that the construction of the vector space and independent set in the first proof was, in fact, a construction of a representation for the cycle matroid of T over . It’s a famous theorem that every graphic matroid is representable over $latex GF(2)$ (and, in fact, over every field) — if this theorem, or more likely a purely matroid-theoretic version, can be proved without recourse to induction or linear algebra, we might obtain a “new” proof that .

Second, the cycle matroid of a simple graph is a simple matroid. In particular, if we consider the representation over of the cycle matroid of analogous to the one we constructed, we have an immediate proof that .

**Questions**: Can we give a “purely matroid-theoretic” proof of ? Can we give a matroid-theoretic proof that exponential functions eventually dominate polynomial functions?

### Like this:

Like Loading...

*Related*

Tags: embarrassing myself, graph theory, high school math, math.CO, matroids, pigeonhole principle

This entry was posted on February 15, 2010 at 08:04 and is filed under blegs, open questions. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply