## 2^n \geq n: The graph theory proof?

Theorem. For every positive integer n, $2^n \geq n$.

Proof. Consider a tree on n vertices $T = (V, E)$ with root $v_0$. Assign to each edge $\{v, w\}$ an element of the vector space $GF(2)^V$, 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 $S \subset E$ sum to 0. There is a natural “distance” function on E w/r/t $v_0$; let $e_0 = \{s, t\}$ have maximal distance in S, and suppose WLOG that t is farther than s from $v_0$. 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 $2^n-1$ 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 $T$ 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 $V \cong GF(2)^n$. 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 $GF(2)$. 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 $2^n \geq n$.

Second, the cycle matroid of a simple graph is a simple matroid. In particular, if we consider the representation over $GF(2)$ of the cycle matroid of $K_n$ analogous to the one we constructed, we have an immediate proof that $2^n \geq \binom{n}{2}$.

Questions: Can we give a “purely matroid-theoretic” proof of $2^n \geq n$? Can we give a matroid-theoretic proof that exponential functions eventually dominate polynomial functions?