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

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.