I am studying this chapter and I am stuck on page 262. In fact, I do not understand why the pair (E, $\tilde{\mathcal{S}}$) is a matroid where $\tilde{\mathcal{S}}$ is the set of all the subsets of all 1-trees on the complete graph $K_n$. Following the definition in Wikipedia, I am supposed to prove three things:

  1. The empty set is in $\tilde{\mathcal{S}}$: this is true, as it is a subset of every set, and thus a subset of every 1-tree.
  2. Every subset of $S\in \tilde{\mathcal{S}}$ is in $\tilde{\mathcal{S}}$ as well: this is trivially true, as every subset of a subset of a 1-tree is a subset of a 1-tree as well.
  3. If $I,J\in\tilde{\mathcal{S}}$ and $\vert I \vert < \vert J \vert $, then there exists $e \in J \setminus I$ such that $I\cup{e}$ is still in $\tilde{\mathcal{S}}$: This is where I am stuck. Consider the following examples: Let $K_5$ be the complete graph on 5 nodes and consider the 1-tree ${(1, 2), (1, 4), (2, 3), (4, 3), (4,5)}$ and let $I = {(1, 2)}$, and $J = {(1, 4), (2, 3)}$. The two sets are both subsets of the original 1-tree, but they are disjoint, so I cannot prove the existence of such $e$.

1 Answer 1


For property 3, $I$, $J$, and $I \cup e$ need not be subsets of the same $1$-tree. In your example, you can take either edge in $J$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.