# Is this similarity between trees and vector space bases just a coincidence?

A vector space basis is a set of vectors that span the space and is linearly independent.

It is well-known that for finite dimensional vector spaces this is equivalent to:

1. The set is minimal with respect to being a spanning set.
2. The set is maximal with respect to being linearly independent.
3. Every element of the vector space is uniquely represented as a linear combination of the basis' vectors.

Now consider finite trees. A tree is defined as a set of edges (for some fixed vertex set) such that they connect the vertices (e.g. the tree is a connected graph) and the set is "independent" in the sense that there are no cycles.

Again, this is equivalent to:

1. The set is minimal with respect to the connectedness of the graph.
2. The set is maximal with respect to the independence (any edge added would create a cycle).
3. For every two vertices, there is a unique path between them in the tree.

The similarity is very striking, I believe.

My question is - is this simply a coincidence or part of a greater (category-theory?) connection I'm unaware of? And are there more instances in mathematics for sets having this "minimal-maximal-unique" set of defining properties?

-
I think the notion you're looking for is a matroid. –  Miha Habič Aug 11 '11 at 11:41
@Miha: Write that as an answer, not as a comment. (Since it is in fact the answer to the question asked!) –  Hans Lundmark Aug 11 '11 at 12:11
It's cool you noticed such a striking resemblance. Cool to know. +1 –  Patrick Da Silva Aug 11 '11 at 12:43
@Hans: I feel that an answer should have more content than just a wiki link, especially since Gadi noticed the similarity by himself. I'm sure someone who has more knowledge (i.e. any at all) about matroids than me will write up an informative answer. –  Miha Habič Aug 11 '11 at 13:04
@Miha: Well, I disagree, for the reason that questions might appear to be unanswered on the front page, when in fact they have already been perfectly answered. (In this case, I don't see any need for writing an answer with yet another tutorial about matroids. A simple link would suffice to find more information and relevant literature. But it's of course possible for someone to add a longer answer later anyway.) –  Hans Lundmark Aug 11 '11 at 13:19