## Posts Tagged ‘matroids’

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

February 15, 2010

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.