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.